P6610 [Code+#7]同余方程
Alex_Wei
·
·
题解
*II. P6610 [Code+#7]同余方程
基础数论学习笔记 Part 7 例 2。
究极神仙题。
根据 \mu(p) \neq 0 不难想到使用 CRT 将问题拆分为模奇质数。每个奇质数的解的个数的积即为所求，因为从每个奇质数的解中任选一个，根据中国剩余定理，所有奇质数对应的解组合起来唯一确定一个解。
拆成奇质数是为了使二次剩余相关定理适用。接下来 p 均视为奇质数。
问题转化为求解 x 能被拆分成多少组 a, b 的和，使得 a, b 均为二次剩余或 0。其中，每个二次剩余的贡献系数是 2（一个二次剩余可被表示两个数的平方），0 的贡献是 1，每组 (a, b) 的贡献即 a 和 b 分别的贡献系数之积。
我们需要一个数学公式而非判断式来描述答案，因为判断式是不可化简的。
二次剩余对应 2，0 对应 1，二次非剩余对应 0，这使得我们想到勒让德符号：注意到 \left(\dfrac a p\right) + 1 等价于使得 x ^ 2 \equiv a \pmod p 的 x 的个数，因此答案为
\sum\limits_{a + b \equiv x} \left(\left(\dfrac a p\right) + 1\right)\left(\left(\dfrac b p\right) + 1\right)
$$
p + \sum\limits_{a = 0} ^ {p - 1} \left(\dfrac {ax - a ^ 2} p\right)
$$
接下来是一步巧妙转化。考虑到为 $ax - a ^ 2$ 除以 $a ^ 2$ 并不影响它的二次剩余性，因此答案即
$$
p + \sum\limits_{a = 1} ^ {p - 1}\left(\dfrac {\frac x a - 1} p\right)
$$
显然，对于 $x \neq 0$ 且 $a \in [1, p - 1]$，$\dfrac x a$ 取遍 $[1, p - 1]$，即 $\dfrac x a - 1$ 取遍 $[0, p - 2]$。故当 $x \neq 0$ 时，答案又可写为
$$
p - \left(\dfrac {-1}{p}\right)
$$
根据欧拉判别准则公式 $\left(\dfrac a p\right) \equiv a ^ {\frac {p - 1} 2} \pmod p$ 上式即 $p - (-1) ^ {\frac {p - 1} 2}$。
对于 $x = 0$，答案 $p + \sum\limits_{a = 1} ^ {p - 1} \left(\dfrac {-1} p\right)$ 即 $p + (p - 1)(-1) ^ {\frac {p - 1} 2}$。
公式已经足够简洁，可以 $\mathcal{O}(1)$ 计算。时间复杂度 $\mathcal{O}(p + n\omega(p))$。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 5;
int T, p, x, cnt, ans = 1, pr[N], mnpr[N];
bool vis[N];
int calc(int x, int p) {return !x ? p % 4 == 1 ? 2 * p - 1 : 1 : p - (p % 4 == 1 ? 1 : -1);}
int main() {
for(int i = 2; i < N; i++) {
if(!vis[i]) mnpr[i] = pr[++cnt] = i;
for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
vis[i * pr[j]] = 1, mnpr[i * pr[j]] = pr[j];
if(i % pr[j] == 0) break;
}
}
cin >> T;
while(T--) {
cin >> p >> x, ans = 1;
while(p != 1) ans *= calc(x % mnpr[p], mnpr[p]), p /= mnpr[p];
cout << ans << "\n";
}
return 0;
}
```