判断 a 是否为质数 p 的原根(p ≤ 10⁹,T ≤ 20)。
对于质数 p,若正整数 g 满足:
1 < g < pg^(p−1) mod p = 11 ≤ i < p−1,都有 g^i mod p ≠ 1则称 g 是 p 的原根。给定 T 组 (a, p),判断 a 是不是 p 的原根。
原根阶费马小定理快速幂质因数分解
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 T;随后 T 行每行 a、p |
| 输出 | 每行 Yes 或 No |
| 数据范围 | 1 ≤ T ≤ 20,3 ≤ p ≤ 10⁹,1 < a < p |
| 保证 | p 是质数 |
| 判定目标 | a 的"阶"是否恰好等于 p−1 |
a^(p−1) ≡ 1 (mod p) 总是成立(当 p 为质数且 p ∤ a);而 a 的阶一定是 p−1 的约数a^((p−1)/q) ≡ 1 (mod p)。只需对 p−1 的每个质因子各测一次幂即可!先把 p − 1 分解质因数。
p − 1 = 998244352
不断除以 2:998244352 = 2²³ × 119
119 = 7 × 17
所以 p − 1 = 2²³ × 7 × 17
不同的质因子是 2、7、17
质因子集合 {2, 7, 17}
对 q = 2:(p−1)/2 = 499122176
对 q = 7:(p−1)/7 = 142606336
对 q = 17:(p−1)/17 = 58720256
只要 a 的这三个幂中有一个 ≡ 1,a 就不是原根
测 3 个幂
| a | a^((p−1)/2) | a^((p−1)/7) | a^((p−1)/17) | 结论 |
|---|---|---|---|---|
| 3 | ≠ 1 | ≠ 1 | ≠ 1 | Yes |
| 5 | ≠ 1 | ≠ 1 | ≠ 1 | Yes |
| 7 | ≠ 1 | = 1 | ≠ 1 | No |
输出 Yes、Yes、No ✓
7^((p−1)/7) ≡ 1 (mod p),说明 7 的阶整除 (p−1)/7,比 p−1 小,所以它不可能遍历全部非零余数("生成"整个乘法群)——它不是原根。取 p = 7(p − 1 = 6 = 2 × 3,质因子 {2, 3})。检查 a = 3 和 a = 2。
| a | a^1 | a^2 | a^3 | a^4 | a^5 | a^6 | 阶 |
|---|---|---|---|---|---|---|---|
| 3 | 3 | 2 | 6 | 4 | 5 | 1 | 6 |
| 2 | 2 | 4 | 1 | 2 | 4 | 1 | 3 |
3 的幂依次是 3, 2, 6, 4, 5, 1
恰好把 1 ~ 6 全部走了一遍
阶 = 6 = p − 1 ✓
用定理验证:(p−1)/2 = 3,3³ = 27 mod 7 = 6 ≠ 1 ✓
(p−1)/3 = 2,3² = 9 mod 7 = 2 ≠ 1 ✓
两个都不为 1 → 是原根
✅ 输出 Yes
2 的幂:2, 4, 1, 2, 4, 1…(周期 3)
只覆盖了 {1, 2, 4},走不到 3、5、6
阶 = 3 ≠ 6
用定理验证:(p−1)/3 = 2,2² = 4 mod 7 = 4 ≠ 1 ✓
(p−1)/2 = 3,2³ = 8 mod 7 = 1 ✗
有一个为 1 → 不是原根
❌ 输出 No
p = 7 的原根是 3 和 5(共 φ(6) = 2 个)
(p−1)/q(q 是 p−1 的某个质因子)。所以只要把 (p−1)/q 这几种指数测一遍就够了。分解 p−1,对每个质因子 q 测 a^((p−1)/q) mod p
(p−1)/q 这些指数。注意乘方时 a*b 可能到 10¹⁸,用 long long 刚好不溢出。对 i = 1…p−2 依次判断 a^i mod p 是否为 1
| 方案 | 单次判定(p = 10⁹) | 可行性 |
|---|---|---|
| 定理 + 快速幂 | 约 3 × 10⁴ | ✅ 稳过 |
| 暴力枚举指数 | 约 10⁹ | ❌ 超时 |
第一行输入 T,随后 T 行输入 a 和 p,程序会分解 p−1 并逐项验证。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; // 快速幂:计算 (b^e) mod m long long powmod(long long b, long long e, long long m) { long long r = 1 % m; b %= m; while (e > 0) { if (e & 1) r = r * b % m; // a*b < 10^18,long long 不会溢出 b = b * b % m; e >>= 1; } return r; } int main() { int T; scanf("%d", &T); while (T--) { long long a, p; scanf("%lld %lld", &a, &p); if (a <= 1 || a >= p) { puts("No"); continue; } long long m = p - 1; // 分解 m,收集不同的质因子 vector<long long> primes; long long t = m; for (long long i = 2; i * i <= t; i++) { if (t % i == 0) { primes.push_back(i); while (t % i == 0) t /= i; // 除干净,只保留"不同"质因子 } } if (t > 1) primes.push_back(t); // 对每个质因子 q,检查 a^((p-1)/q) mod p 是否等于 1 bool ok = true; for (long long q : primes) { if (powmod(a, m / q, p) == 1) { ok = false; break; } } puts(ok ? "Yes" : "No"); } return 0; }
a^((p−1)/q) ≡ 1 就说明不是原根"?设 a 的阶为 d(最小的使 a^d ≡ 1 的正整数)。若 a^((p−1)/q) ≡ 1,则 d 整除 (p−1)/q,所以 d ≤ (p−1)/q < p−1——阶小于 p−1,不是原根。d 整除 p−1 且 d ≠ p−1,于是存在 p−1 的质因子 q 使 d | (p−1)/q,从而 a^((p−1)/q) ≡ 1。两个方向都成立,所以判定是充要的。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (e & 1) r = r * b % m; | 快速幂 | 二进制幂,O(log e) |
while (t % i == 0) t /= i; | 分解去重 | 只要不同质因子,所以除干净 |
if (t > 1) primes.push_back(t); | 剩余质因子 | 试除结束后剩下的必是质数 |
powmod(a, m / q, p) == 1 | 判定 | 只要一个为 1 就不是原根 |
i = 1…p−1 暴力判(p 达 10⁹ 必超时);② 分解时不去重(会把同一个质因子测很多遍,虽然不影响正确性但浪费时间);③ 快速幂里 r * b 用 int 会溢出;④ 忘记检查 1 < a < p(题目保证 a < p,但养成校验习惯)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | Yes Yes No | 题面样例 |
2 | Yes No | p = 7:3 是原根(3⁶ 走遍 1~6),2 不是(2³ ≡ 1) |
2 | Yes No | p = 3:2 是原根;5 超出范围应输出 No |
1 | No | a = 1 不满足 a > 1 |
3 | Yes Yes No | 重复验证题面样例 |
a * b 可达 10¹⁸,要用 long long。只需存下质因子列表(很短)。
✅ 约 60 万次操作,瞬间完成。关键在于把"检查 p−2 个指数"压缩成"检查几个质因子对应的指数"。
// 快速幂模板 long long powmod(long long b, long long e, long long m) { long long r = 1 % m; b %= m; while (e > 0) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; } return r; } // 分解并收集"不同质因子" vector<long long> distinctPrimes(long long x) { vector<long long> v; for (long long i = 2; i * i <= x; i++) if (x % i == 0) { v.push_back(i); while (x % i == 0) x /= i; } if (x > 1) v.push_back(x); return v; } // 与本题相关的数论结论 // - 费马小定理:p 为质数且 p ∤ a 时 a^(p-1) ≡ 1 (mod p) // - 阶 d 必整除 p-1 // - a 是原根 <=> 对 p-1 的每个质因子 q,a^((p-1)/q) ≢ 1 (mod p) // - p 的原根个数 = φ(p-1) // - 求最小原根可以从 2 开始逐个试,通常很快
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 快速幂 | 二进制幂,O(log e) | 所有大指数取模问题 |
| 阶与整除 | a 的阶必整除 p−1 | 原根、离散对数、循环群 |
| 质因子筛选 | 只需测 p−1 的质因子对应幂 | "把 O(p) 判定压到 O(log p)"的关键 |