为谁而为
题目背景
在考完轻花学院的炼金术应用奥数期中考试后,小水母正准备开始炼金术系统概论与显求导 W(-2) 的期中复习。此时她接到音乐老师的电话,要为芙兰郡的炼金术学徒们准备一些新颖药剂。几天内毫无头绪的她,只好尝试改造刚获得的药剂。没有完成前两个任务的学徒们,不必在此尝试过久。
对于还不会酿造茜珀拉药剂的学徒,题面下方准备了附有解释的炼药药方。
题目描述
给定非负整数 a,b 和素数 p,求有序整数对 (x,y) 的数量,使得
0≤x,y<p,y2≡x3+ax+b(modp).
只统计上述有限范围内的整数对,不计射影曲线的无穷远点。共有 T 次独立询问,输出每次询问的准确数量,不取模。
系数 a,b 可以先按模 p 化为对应的余数;题目给出的范围并未要求 a,b<p。
输入格式
从标准输入读入。
第一行一个正整数 T。
接下来 T 行,每行三个整数 a,b,p。
输出格式
向标准输出输出 T 行,每行一个非负整数表示对应询问的答案。
样例输入 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
原题另附样例 2 至 4;现有附件中未包含这些样例文件。
数据范围
所有数据满足 1≤T≤10,0≤a,b≤1018,2≤p≤1018,保证 p 为素数。
| 测试点 |
p≤ |
特殊性质 |
| 1 |
100 |
无 |
| 2 |
106 |
| 3 |
109 |
A |
| 4 |
| 5 |
B |
| 6 |
无 |
| 7 |
1018 |
A |
| 8 |
B |
| 9 |
无 |
| 10 |
- 性质 A:T=1。
- 性质 B:每组询问均满足 4a3+27b2≡0(modp)。
小水母的提示
在模素数 p 的运算中,开平方可以使用 Cipolla 算法。下面的算法说明针对奇素数 p;当 p=2 时可以直接检查两个可能的余数。
称 n 是模 p 的二次剩余,当且仅当 x2≡n(modp) 有解。n=0 时唯一的余数解是 x=0。以下说明考虑非零 n:每个非零二次剩余恰好对应两个互为相反数的平方根,所以非零二次剩余共有 (p−1)/2 个;若把 0 也计入,则共有 (p+1)/2 个。
欧拉准则:对非零 n,它是二次剩余当且仅当
n(p−1)/2≡1(modp).
若 n 为非零二次剩余,通过随机化寻找 c,使 c2−n 是非二次剩余,期望尝试次数为 O(1)。引入符号 λ,规定 λ2=c2−n,并在形如 A+Bλ 的元素构成的扩域中计算。
令
u=(c+λ)(p+1)/2.
因为 c2−n 是非二次剩余,故
λp=λ(λ2)(p−1)/2=−λ.
于是
$$u^2=(c+\lambda)^{p+1}=(c^p+\lambda^p)(c+\lambda)=(c-\lambda)(c+\lambda)=n.$$
又由于 n(p−1)/2=1,有 up=u,因此 u 实际属于原来的模 p 域,不带 λ 项,便得到 x2≡n(modp) 的一个解。
原题另下发了一份附有注释的 Cipolla 参考实现,可以结合上述说明使用;现有附件中未包含这份参考代码。