自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:22:24，当前版本为作者最后更新于2022-03-28 21:33:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

*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_{i = 0} ^ {p - 1} \left(\dfrac i p\right) = 0$。再根据 $b \equiv x - a$ 和勒让德符号的完全积性，上式简化为

$$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))$。

#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;
}