[GESP202503 五级] 原根判断
小 A 知道，对于质数 \(p\) 而言，\(p\) 的原根 \(g\) 是满足以下条件的正整数：
- \(1 < g < p\)
- \(g^{p - 1} \bmod p = 1\)
- \(\forall i, 1 \leq i < p - 1\) ，均有 \(g^{i} \bmod p \neq 1\)
小 A 现在有一个整数 \(a\)，请你帮他判断 \(a\) 是不是 \(p\) 的原根。
做法：
如果学过原根，能不看题目给的条件，直接用比较好的方法做！
但是，通过充分挖掘题目给出的信息，只需要懂“整除、同余”，再配合数学归纳就能做！
显然我们知道 \(g^{0} \bmod p = 1\) 。题目的第 \(2\) 个条件又告诉了我们 \(g^{p - 1} \bmod p = 1\) ，那么说明在 \(\bmod p\) 意义下，\(0 = p-1\) 。
稍微分析一下前几项
\[\begin{aligned}
g^{0} \bmod p &= g^{p-1} \bmod p \\
g^{1} \bmod p &= g^{0 + 1} = g^{p-1 + 1} = g^{p} \bmod p \\
g^{2} \bmod p &= g^{0 + 2} = g^{p-1 + 2} = g^{p+1} \bmod p \\
\end{aligned}
\]
数学归纳后面的项数
\[\begin{aligned}
g^{0 + x} \bmod p &= g^{p-1 + x} \bmod p \\
\end{aligned}
\]
从上面的通项归纳出每 \(p - 1\) 个数是一个循环。
现在虽然知道了 \(p-1\) 是一个循环，但我们不保证 \(p-1\) 是最小的循环。若存在 \(i\) 满足 \(0 < i < p-1\) 且 \(a^{i} \bmod p = 1\) ，那么 \(i\) 就是一个更小的循环( \(i\) 是循环证明方法和上面的归纳法一样)。
缺什么来什么，刚好现在题目的第 \(3\) 个条件又告诉我们 \(\forall i, 1 \leq i < p - 1\) ，均有 \(g^{i} \bmod p \neq 1\) ，那么说明不存这样的 \(i\) 。
于是 \(p-1\) 就是最小的循环。
根据整除性质，小的循环整除大的循环，即小的循环是大的循环的因子。
于是做法就是，我们先判断 \(p-1\) 是一个循环。然后分解 \(p-1\) 的因子，他的所有因子都不能是循环。
于是代码呼之欲出。实现的时候我们其实要知道怎么做快速幂，怎么做质因子分解。
view
#include <bits/stdc++.h>
using namespace std;typedef long long i64;i64 ksm(i64 a, i64 n, int m) {i64 res = 1;for( ;n; n >>= 1, a = a * a % m) {if (n & 1) {res = res * a % m;}}return res;
}int SOLVE() {int a, p;cin >> a >> p;assert(ksm(2, 3, p) == 8 % p);if (ksm(a, p - 1, p) != 1) {// 如果 p - 1 不是循环，坏了return -1;}for (int i = 2; i * i <= p - 1; i++) {if ((p - 1) / i * i == p - 1) {// 分解出 p - 1 的共轭因子 u 和 vint u = i, v = (p - 1) / u;if (ksm(a, u, p) == 1 || ksm(a, v, p) == 1) {// 如果 u 是循环，或者 v 是循环，说明 p - 1 不是最小循环，坏了return -1;}}}// 一切安好return 0;
}signed main() {int T = 1;for (cin >> T; T--; ) {int ac = SOLVE();cout << (ac == 0 ? "Yes" : "No") << "\n";}return 0;
}