P6610 题解
JerryTcl
·
·
题解
旧题解错误：云剪贴板
来整一个更注重于观察结构而不是计算的题解（
首先使用 CRT 将问题转化为模奇质数的结果相乘是显然的。
考虑对于 a ^ 2 + b ^ 2 的经典转化：我们引入 i ^ 2 = -1，那么也即 (a + bi)(a - bi) \equiv x \pmod p。
根据一些代数知识，容易知道 i \in \mathbb Z_p \iff \operatorname{ord}(i) \mid p - 1 \iff p = 4k + 1，故以下分 p = 4k + 1 与 p = 4k + 3 讨论。
要求的即是 $uv \equiv x \pmod p$ 的解数。
$x = 0$ 时有 $u = 0$ 或 $v = 0$，答案为 $2p-1$；
$x \neq 0$ 时可以任意取 $u$ 后唯一确定 $v$，答案为 $p-1$。
$p=4k+3$ 时，$i \notin \mathbb Z_p$，故在 $\mathbb Z_p[i]$ 上考虑。
我们定义范数 $N(z) = z\bar{z}$，则 $N(a+bi) = a^2+b^2$。
容易验证 $N(zw) = N(z)N(w)$，我们要求的就是 $\mathbb Z_p[i]$ 中元素在范数映射下的原像大小。
$\mathbb Z_p[i]$ 作为 $p^2$ 个元素的有限域 $\mathbb F_{p^2}$，有原根存在定理，即其乘法群为循环群。
设其一个原根为 $\gamma$，我们证明，$N(\gamma) = g$ 是 $\mathbb Z_p$ 的原根。
$\mathbb Z_p[i]$ 作为 $x^2+1$ 在 $\mathbb Z_p$ 上的分裂域，其 Galois 群为 $i \mapsto -i$。
同时，$\mathbb Z_p[i]$ 存在域扩张 $\mathbb F_{p^2} / \mathbb F_p$，其 Galois 群为 Frobenius 自同构 $x \mapsto x^p$。
对比可知 $(a+bi)^p = a-bi$，计算可以验证这个结果，故 $N(z) = z\bar{z} = z z^p = z^{p+1}$。
故 $g = \gamma^{p+1}$。根据原根的定义，$1, \gamma^{p+1}, \gamma^{2(p+1)}, \cdots$ 互不相同，故 $g$ 是 $\mathbb Z_p$ 的原根。
然后就容易了，对于 $i=0\sim p^2-2$，有 $N(\gamma^i) = g^i$，
故 $x=1 \sim p-1$ 各被取到 $(p^2-1)/(p-1) = p+1$ 次。
剩下一个 $N(0) = 0$，即 $x=0$ 时的答案为 $1$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
inline int Calc(int x, int p) { return p & 2 ? x ? p + 1 : 1 : x ? p - 1 : 2 * p - 1; }
void Solve() {
int x, m, ans = 1; cin >> m >> x;
for(int i = 2; i * i <= m; ++i)
if(m % i == 0) ans *= Calc(x % i, i), m /= i;
printf("%d\n", m == 1 ? ans : ans * Calc(x % m, m));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T; while(T--) Solve();
}
```