GESP 题解库 / 5 级题解 / [GESP202503 五级] 原根判断 · 第 9 / 23 题
GESP202503 五级 · P11961 · 困难

原根判断

判断 a 是否为质数 p 的原根(p ≤ 10⁹,T ≤ 20)。

📊
T ≤ 20, p ≤ 10⁹
数据范围
🔢
long long
数值类型
⚡
O(T √p log p)
时间复杂度
🎯
快速幂 + 质因数分解
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

对于质数 p,若正整数 g 满足:

则称 g 是 p 的原根。给定 T 组 (a, p),判断 a 是不是 p 的原根。

⚠️
题目自己说明了:这题可能超出 GESP 考纲(原根是 NOI 8 级知识点,相对简单的费马小定理/欧拉定理也是 7 级)。所以这道题更适合当成"拓展学习",理解其中的数论思想比背代码更重要。

🔍 关键词提取

原根阶费马小定理快速幂质因数分解

已知条件

项目说明
输入第一行 T;随后 T 行每行 a、p
输出每行 Yes 或 No
数据范围1 ≤ T ≤ 20,3 ≤ p ≤ 10⁹,1 < a < p
保证p 是质数
判定目标a 的"阶"是否恰好等于 p−1

需要解决的问题

02
思维导图
整理解题思路的全貌
🔮 阶 = p−1?只需查质因子
📚 基础概念
a 的"阶" = 最小的 d 使 a^d ≡ 1
费马小定理:a^(p−1) ≡ 1
所以阶必整除 p−1
原根 = 阶恰好等于 p−1
🔍 判定转化
若阶 ≠ p−1,则它整除 (p−1)/q
q 为 p−1 的某个质因子
等价于 a^((p−1)/q) ≡ 1
所以只需测这些幂
⚙️ 实现
分解 p−1 得全部不同质因子
对每个 q 算 a^((p−1)/q) mod p
任一为 1 → 不是原根
还要校验 a^(p−1) ≡ 1
⚠️ 易错点
枚举 i 到 p−1(不可能)
乘方时中间结果溢出
只测 p−1 的最大质因子
混淆"质因子"与"质因数(含重数)"
03
样例手算推导
样例的完整判定过程

🧮 样例:p = 998244353,a = 3 / 5 / 7

先把 p − 1 分解质因数。

1
分解 p − 1

p − 1 = 998244352

不断除以 2:998244352 = 2²³ × 119

119 = 7 × 17

所以 p − 1 = 2²³ × 7 × 17

不同的质因子是 2、7、17

质因子集合 {2, 7, 17}

2
需要检查的幂

对 q = 2:(p−1)/2 = 499122176

对 q = 7:(p−1)/7 = 142606336

对 q = 17:(p−1)/17 = 58720256

只要 a 的这三个幂中有一个 ≡ 1,a 就不是原根

测 3 个幂

aa^((p−1)/2)a^((p−1)/7)a^((p−1)/17)结论
3≠ 1≠ 1≠ 1Yes
5≠ 1≠ 1≠ 1Yes
7≠ 1= 1≠ 1No

输出 Yes、Yes、No ✓

🔑
注意 a = 7 时为什么不是原根:因为 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。

aa^1a^2a^3a^4a^5a^6阶
33264516
22412413
1
a = 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
a = 2 不是原根

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"意味着"存在更小的指数让 a 回到 1",而这样的更小指数一定整除 (p−1)/q(q 是 p−1 的某个质因子)。所以只要把 (p−1)/q 这几种指数测一遍就够了。
04
解法对比
定理判定 vs 暴力枚举 i

⚔️ 解法对比

🟢 定理判定 + 快速幂(推荐) 推荐

分解 p−1,对每个质因子 q 测 a^((p−1)/q) mod p

  • 每次判定 O(√p + ω(p−1) log p)
  • p = 10⁹ 时约 3 × 10⁴ + 几十次幂
  • 代码 45 行
  • 有数论定理保证
💡
三个必备组件:① 快速幂(二进制幂,O(log p));② 质因数分解(试除到 √(p−1));③ 结论——只需检查 (p−1)/q 这些指数。注意乘方时 a*b 可能到 10¹⁸,用 long long 刚好不溢出。

🟠 暴力枚举指数 i

对 i = 1…p−2 依次判断 a^i mod p 是否为 1

  • 时间 O(p) = 10⁹
  • T = 20 时高达 2 × 10¹⁰
  • 必然超时
  • 只适用于 p ≤ 10³ 的测试点
⚠️
注意数据分档:40% 的测试点 p ≤ 10³(暴力可得 40 分),但全部测试点 p ≤ 10⁹,想满分必须用定理。

📈 性能对比

方案单次判定(p = 10⁹)可行性
定理 + 快速幂约 3 × 10⁴✅ 稳过
暴力枚举指数约 10⁹❌ 超时
05
算法流程图
分解 p−1 后逐个质因子验证
开始读入 T,循环处理每组 (a, p)把 m = p − 1 做质因数分解,得到不同质因子的集合 Qa 是否满足 1 < a < p?是 ✓继续判定否 ✗输出 No遍历 Q 中每个质因子 q计算 a^((p−1)/q) mod p(用快速幂)结果是否等于 1?是 ✓不是原根,输出 No否 ✗继续检查下一个 q所有 q 都检查完且都不为 1 → 输出 Yes结束取下一个质因子
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔮 原根判定器

第一行输入 T,随后 T 行输入 a 和 p,程序会分解 p−1 并逐项验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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 且 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,但养成校验习惯)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
3 998244353 / 5 998244353 / 7 998244353
Yes
Yes
No
题面样例
2
3 7 / 2 7
Yes
No
p = 7:3 是原根(3⁶ 走遍 1~6),2 不是(2³ ≡ 1)
2
2 3 / 5 3
Yes
No
p = 3:2 是原根;5 超出范围应输出 No
1
1 7
Noa = 1 不满足 a > 1
3
3 998244353 / 5 998244353 / 7 998244353
Yes
Yes
No
重复验证题面样例
✅
自查清单:① 分解了 p−1 吗?② 测了每个质因子吗?③ 快速幂用 long long 吗?

🚨 易错点清单

⚠️
暴力枚举指数:p 达 10⁹,枚举 i 到 p−1 必然超时,必须用"只测 p−1 的质因子对应幂"这个定理。
⚠️
快速幂溢出:模数 p ≤ 10⁹,a * b 可达 10¹⁸,要用 long long。
⚠️
只测最大质因子:必须测 p−1 的每一个不同质因子。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(√p + ω(p−1) · log p)
空间复杂度
O(1)
T 最大
20
单次判定
约 3 × 10⁴

时间怎么算的?

空间都用在哪?

只需存下质因子列表(很短)。

✅ 约 60 万次操作,瞬间完成。关键在于把"检查 p−2 个指数"压缩成"检查几个质因子对应的指数"。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 快速幂模板
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)"的关键
🌟
思考题:如果题目改成"求 p 的最小原根",该怎么做?(提示:从 2 开始逐个试,对每个候选用本题的判定方法检查,找到第一个通过的即可。理论上可以证明最小原根是 O(p^(1/4+ε)) 级别的,所以实践中很快。它属于 NOIP 提高组 / NOI 级别的数论内容,这里作为拓展了解即可。)