#P6574. 为谁而为

为谁而为

为谁而为

题目背景

在考完轻花学院的炼金术应用奥数期中考试后,小水母正准备开始炼金术系统概论与显求导 W(-2) 的期中复习。此时她接到音乐老师的电话,要为芙兰郡的炼金术学徒们准备一些新颖药剂。几天内毫无头绪的她,只好尝试改造刚获得的药剂。没有完成前两个任务的学徒们,不必在此尝试过久。

对于还不会酿造茜珀拉药剂的学徒,题面下方准备了附有解释的炼药药方。

题目描述

给定非负整数 a,ba,b 和素数 pp,求有序整数对 (x,y)(x,y) 的数量,使得

0≤x,y<p,y2≡x3+ax+b(modp).0\leq x,y<p,\qquad y^2\equiv x^3+ax+b\pmod p.

只统计上述有限范围内的整数对,不计射影曲线的无穷远点。共有 TT 次独立询问,输出每次询问的准确数量,不取模。

系数 a,ba,b 可以先按模 pp 化为对应的余数;题目给出的范围并未要求 a,b<pa,b<p。

输入格式

从标准输入读入。

第一行一个正整数 TT。

接下来 TT 行,每行三个整数 a,b,pa,b,p。

输出格式

向标准输出输出 TT 行,每行一个非负整数表示对应询问的答案。

样例输入 1

6
0 0 2
0 1 3
4 4 5
6 0 7
6 1 7
6 4 7

样例输出 1

2
3
7
7
11
9

原题另附样例 22 至 44;现有附件中未包含这些样例文件。

数据范围

所有数据满足 1≤T≤101\leq T\leq10,0≤a,b≤10180\leq a,b\leq10^{18},2≤p≤10182\leq p\leq10^{18},保证 pp 为素数。

测试点 p≤p\leq 特殊性质
11 100100 无
22 10610^6
33 10910^9 A
44
55 B
66 无
77 101810^{18} A
88 B
99 无
1010
  • 性质 A:T=1T=1。
  • 性质 B:每组询问均满足 4a3+27b2≡0(modp)4a^3+27b^2\equiv0\pmod p。

小水母的提示

在模素数 pp 的运算中,开平方可以使用 Cipolla 算法。下面的算法说明针对奇素数 pp;当 p=2p=2 时可以直接检查两个可能的余数。

称 nn 是模 pp 的二次剩余,当且仅当 x2≡n(modp)x^2\equiv n\pmod p 有解。n=0n=0 时唯一的余数解是 x=0x=0。以下说明考虑非零 nn:每个非零二次剩余恰好对应两个互为相反数的平方根,所以非零二次剩余共有 (p−1)/2(p-1)/2 个;若把 00 也计入,则共有 (p+1)/2(p+1)/2 个。

欧拉准则:对非零 nn,它是二次剩余当且仅当

n(p−1)/2≡1(modp).n^{(p-1)/2}\equiv1\pmod p.

若 nn 为非零二次剩余,通过随机化寻找 cc,使 c2−nc^2-n 是非二次剩余,期望尝试次数为 O(1)O(1)。引入符号 λ\lambda,规定 λ2=c2−n\lambda^2=c^2-n,并在形如 A+BλA+B\lambda 的元素构成的扩域中计算。

令

u=(c+λ)(p+1)/2.u=(c+\lambda)^{(p+1)/2}.

因为 c2−nc^2-n 是非二次剩余,故

λp=λ(λ2)(p−1)/2=−λ.\lambda^p=\lambda(\lambda^2)^{(p-1)/2}=-\lambda.

于是

$$u^2=(c+\lambda)^{p+1}=(c^p+\lambda^p)(c+\lambda)=(c-\lambda)(c+\lambda)=n.$$

又由于 n(p−1)/2=1n^{(p-1)/2}=1,有 up=uu^p=u,因此 uu 实际属于原来的模 pp 域,不带 λ\lambda 项,便得到 x2≡n(modp)x^2\equiv n\pmod p 的一个解。

原题另下发了一份附有注释的 Cipolla 参考实现,可以结合上述说明使用;现有附件中未包含这份参考代码。