247. 原根判断

markdown
复制
1# 原根判断 题解
2
3## 题目分析
4
5本题要求判断给定的正整数 $a$ 是否为质数 $P$ 的原根。  
6对于质数 $P$，原根 $g$ 定义为：$g$ 的阶恰好等于 $P-1$，即最小的正整数 $k$ 使得 $g^k \equiv 1 \pmod P$ 是 $k = P-1$。
7
8数据范围：$T \le 20$，$3 \le P \le 10^9$，$P$ 为质数。  
9我们需要在 $O(\sqrt{P})$ 或更优的时间内完成单组判断。
10
11---
12
13## 解题思路
14
15### 1. 原根的判定定理
16
17根据数论知识，$a$ 是质数 $P$ 的原根，当且仅当对于 $P-1$ 的**每一个质因子** $q$，都满足：
18
19$$
20a^{\frac{P-1}{q}} \not\equiv 1 \pmod P
21$$
22
23这是因为 $a$ 的阶一定是 $P-1$ 的约数。如果存在某个质因子 $q$ 使得 $a^{(P-1)/q} \equiv 1$，那么 $a$ 的阶至多是 $\frac{P-1}{q}$，不可能是 $P-1$，因此 $a$ 不是原根。  
24反之，若对所有质因子都不成立，则阶必然是 $P-1$，$a$ 就是原根。
25
26### 2. 算法流程
27
281. 读入 $a, P$。
292. 计算 $\varphi = P-1$，对其进行**质因数分解**，得到所有不同的质因子。
303. 对每个质因子 $q$，计算 $a^{\varphi / q} \bmod P$，若结果为 $1$，直接判定为 `No`。
314. 若所有质因子检验均不满足，输出 `Yes`。
32
33---
34
35## 算法说明
36
37### 质因数分解
38
39由于 $P \le 10^9$，$\sqrt{P} \le 31623$，可以直接用试除法枚举 $2$ 到 $\sqrt{P-1}$，找出所有质因子。  
40注意 $P-1$ 可能很大，但试除的复杂度 $O(\sqrt{P})$ 对于每组数据是可以接受的（$T \le 20$ 时，$20 \times 31623 \approx 6\times 10^5$）。
41
42### 快速幂
43
44计算 $a^b \bmod P$ 需要使用**快速幂**（二进制取幂），时间复杂度 $O(\log b)$。  
45因为 $P \le 10^9$，乘法时可能溢出 32 位整数，需要使用 `long long` 进行中间运算。
46
47### 完整步骤
48
49- 对于每一组数据：
50  - 令 $phi = P - 1$，暂存 $tmp = phi$ 用于分解。
51  - 从 $i = 2$ 枚举到 $\sqrt{phi}$：
52    - 若 $tmp \bmod i == 0$：
53      - 说明 $i$ 是 $phi$ 的一个质因子，执行 `check(i)`：若 $a^{phi / i} \bmod P == 1$，则 `ans = false`。
54      - 不停地从 $tmp$ 中除去因子 $i$，直到 $tmp$ 不再被 $i$ 整除。
55  - 循环结束后，若 $tmp > 1$，说明 $tmp$ 本身是一个大于 $\sqrt{phi}$ 的质因子，同样执行 `check(tmp)`。
56  - 根据 `ans` 输出 `Yes` 或 `No`。
57
58---
59
60## 时间复杂度分析
61
62- 质因数分解部分：$O(\sqrt{P})$。
63- 对每个质因子进行一次快速幂，快速幂复杂度 $O(\log P)$。质因子个数不超过 $\log_2 P$，故检验部分 $O(\log^2 P)$。
64- 总复杂度 $O(T(\sqrt{P} + \log^2 P))$，在本题数据范围下完全可行。
65
66---
67
68## 参考代码（正确实现）
69
70```cpp
71#include <cstdio>
72#include <cmath>
73using namespace std;
74
75typedef long long ll;
76
77// 快速幂：计算 a^e mod p
78ll mod_pow(ll a, ll e, ll p) {
79    ll res = 1;
80    a %= p;
81    while (e) {
82        if (e & 1) res = (res * a) % p;
83        a = (a * a) % p;
84        e >>= 1;
85    }
86    return res;
87}
88
89bool is_primitive_root(ll a, ll p) {
90    ll phi = p - 1;
91    ll tmp = phi;
92    // 枚举 phi 的所有质因子
93    for (ll i = 2; i * i <= tmp; ++i) {
94        if (tmp % i == 0) {
95            // i 是质因子
96            if (mod_pow(a, phi / i, p) == 1)
97                return false;
98            while (tmp % i == 0) tmp /= i;
99        }
100    }
101    if (tmp > 1) {  // 剩余一个大于 sqrt 的质因子
102        if (mod_pow(a, phi / tmp, p) == 1)
103            return false;
104    }
105    return true;
106}
107
108int main() {
109    int T;
110    scanf("%d", &T);
111    while (T--) {
112        ll a, p;
113        scanf("%lld%lld", &a, &p);
114        if (is_primitive_root(a, p))
115            printf("Yes\n");
116        else
117            printf("No\n");
118    }
119    return 0;
120}

代码说明

• mod_pow 函数实现快速幂，注意使用 long long 避免乘法溢出。
• is_primitive_root 函数对 $P-1$ 进行质因数分解，利用定理逐一检验。
• 分解时，一旦找到一个质因子 $i$，就检验 $a^{(P-1)/i} \bmod P$，同时将 $tmp$ 中的所有因子 $i$ 全部除去，确保每个质因子只检验一次。
• 最后如果 tmp > 1，说明剩下一个未检验的大质因子，继续检验。

---

关于原参考代码的说明

题目提供的参考代码中存在明显错误：
在快速幂函数 fpw 中，使用了一个固定数字 111 进行取模和乘法，例如：

cpp
复制
1r = 111 * r % p;
2if (e & 1) r = 111 * r * b % p;

这会导致无论输入是什么，计算的结果都与正确的 $a^e \bmod P$ 无关。
可能原因：该代码是测试或混淆版本，111 并非正确的乘法因子。
正确做法：应当使用标准的快速幂算法，如上文正确代码所示。

在理解题意和算法时，请以“原根判定定理”为准，不要参考该代码中的错误部分。

---

总结

• 判断原根的本质是检验 $a$ 对 $P-1$ 的所有质因子 $q$ 是否满足 $a^{(P-1)/q} \not\equiv 1$。
• 时间复杂度 $O(\sqrt{P})$ 分解质因数，完全足够通过本题。
• 注意使用 long long 避免溢出，快速幂正确实现。