文章

【GESP】C++五级真题（数论考点） luogu-P11961 [GESP202503 五级] 原根判断

发表于
作者 OneCoder
次浏览 11 分钟阅读

GESP C++ 2025年3月五级真题，数论考点，可能很超纲的题目，题目难度⭐⭐⭐★☆，五级来说很难。洛谷难度等级提高+/省选−

luogu-P11961 [GESP202503 五级] 原根判断

题目要求

题目背景

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），而相对简单的无需原根知识的做法中，使用的费马小定理与欧拉定理也属于 NOI 大纲 7 级知识点（提高级），且均未写明于 GESP 大纲中。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。

若对题目中原根这一概念感兴趣，可以学习完成 【模板】原根。

题目描述

小 A 知道，对于质数 $p$ 而言，$p$ 的原根 $g$ 是满足以下条件的正整数：

  • $1<g<p$；
  • $g^{p-1}\bmod{p}=1$；
  • 对于任意 $1\le i<p-1$ 均有 $g^i\bmod{p}\neq1$。

其中 $a\bmod{p}$ 表示 $a$ 除以 $p$ 的余数。

小 A 现在有一个整数 $a$，请你帮他判断 $a$ 是不是 $p$ 的原根。

输入格式

第一行，一个正整数 $T$，表示测试数据组数。

每组测试数据包含一行，两个正整数 $a,p$。

输出格式

对于每组测试数据，输出一行，如果 $a$ 是 $p$ 的原根则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1
1
2
3
4

3
3 998244353
5 998244353
7 998244353
输出 #1
1
2
3

Yes
Yes
No

说明/提示

数据范围

对于 $40\%$ 的测试点，保证 $3\le p\le10^3$。

对于所有测试点，保证 $1\le T\le20$，$3\le p\le10^9$，$1<a<p$，$p$ 为质数。

题目分析

说实话，我觉得这道题挺朝纲的，对于GESP5级低年级考生来说，似乎过于难了。我也是学习了很久，才理解相关定理，给出代码示例的。

1. 通俗理解：什么是“原根”？

题目中给了三个条件，我们来翻译一下。假设模数 $p$ 是一个质数（比如 $p=7$）。

  • 条件 1： $1 < a < p$。（这只是限制 $a$ 的范围，输入保证了，不用管）
  • 条件 2： $a^{p-1} \bmod p = 1$。（根据费马小定理，只要 $p$ 是质数且 $a$ 不是 $p$ 的倍数，这个条件恒成立，所以也不用特意检查）
  • 条件 3（核心）： 对于任意 $1 \le i < p-1$，都有 $a^i \bmod p \neq 1$。

通俗解释： 你可以把 $a$ 看作一个发电机，它通过不断地自乘（$a^1, a^2, a^3 \dots$）在模 $p$ 的世界里生成数字。

  • $a$ 的 $p-1$ 次方必须回到 1（这是终点）。
  • 但是，原根要求这个“发电机”必须跑完整个 $1$ 到 $p-1$ 的所有路程，最后一步（第 $p-1$ 步）才能回到 1。
  • 如果它提前（在第 $i$ 步，其中 $i < p-1$）就变回了 1，那它就偷懒了，它就不是原根。

举个例子 ($p=7$)： 我们要检查 $a=2$ 是不是原根。我们需要看 $2^1$ 到 $2^6$。

  • $2^1 \equiv 2$
  • $2^2 \equiv 4$
  • $2^3 \equiv 1$ 👉 注意：这里 $2^3$ 就已经是 1 了。
  • 因为 $3 < 6$，它提前回到了 1。所以 2 不是 7 的原根。

再检查 $a=3$：

  • $3^1 \equiv 3$
  • $3^2 \equiv 2$
  • $3^3 \equiv 6$
  • $3^4 \equiv 4$
  • $3^5 \equiv 5$
  • $3^6 \equiv 1$ 👉 只有到了最后一步 $p-1=6$ 才等于 1。
  • 中间没有提前回到 1，所以 3 是 7 的原根。

2. 解题思路：如何快速判断？

暴力做法（会超时）

最直接的想法是写一个循环，从 $i = 1$ 到 $p-2$，挨个计算 $a^i \bmod p$，看是否等于 1。

  • 如果有一个等于 1，输出 No。
  • 如果都没有，输出 Yes。

问题： $p$ 最大是 $10^9$。如果你循环 $10^9$ 次，程序会跑好几秒甚至超时（计算机一秒大概跑 $10^8$ 次）。

数论优化做法（正解）

我们需要用到一个数学结论： 如果 $a$ 会“提前”回到 1，那么它回到 1 的步数（指数）一定是 $p-1$ 的约数。

更进一步，经过推导可以得出判定原根的充要条件： 对于 $p-1$ 的每一个质因数 $q$，如果都满足： \(a^{\frac{p-1}{q}} \bmod p \neq 1\) 那么 $a$ 就是原根。

只要有一个质因数 $q$ 使得 $a^{\frac{p-1}{q}} \bmod p = 1$，那么 $a$ 就不是原根。

这样，算法步骤就简单了。

3. 算法步骤

为了判断 $a$ 是否为 $p$ 的原根，我们需要做三件事：

  1. 计算 $X = p-1$。
  2. 对 $X$ 进行质因数分解。
    • 找出 $p-1$ 的所有不同的质因子 $q_1, q_2, \dots, q_k$。
    • 例如：如果 $p=7$，则 $p-1=6$，质因子是 2 和 3。
    • 例如：如果 $p=17$，则 $p-1=16 = 2^4$，唯一的质因子是 2。
  3. 进行快速幂检测。(这部分算法，后续详细介绍，常用算法)
    • 对于每一个质因子 $q$，计算 $val = a^{\frac{p-1}{q}} \bmod p$。
    • 如果发现某个 $val == 1$，说明它“提前”回到了 1，判定失败 (No)。
    • 如果所有质因子测试完，都没有出现 1，判定成功 (Yes)。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <algorithm>
#include <iostream>
#include <vector>

// 快速幂取模函数
// 计算 (base^exp) % mod
// 使用 long long 防止中间结果溢出
long long power_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        // 如果指数是奇数，将当前的 base 乘入结果
        if (exp & 1) {
            result = result * base % mod;
        }
        // base 自乘，指数右移一位（除以 2）
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    // 优化 I/O 操作
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T;
    std::cin >> T;
    while (T--) {
        int a, p;
        std::cin >> a >> p;

        // 条件 1: 1 < a < p，题目数据自然满足
        // 条件 2: 费马小定理：如果 p 是质数，则 a^(p-1) mod p = 1
        // 恒成立，题目保证 p 是质数，自然满足，无需额外判断。

        // 条件 3 的等价判定：
        // 对于 p-1 的任意质因数 q，如果 a^((p-1)/q) mod p == 1，则 a 不是原根。
        // 这种方法比枚举所有 1 <= i < p-1 更高效。
        int target = p - 1;
        std::vector<int> primes;

        // 分解质因数：找出 p-1 的所有不同质因数
        for (int i = 2; i * i <= target; i++) {
            if (target % i == 0) {
                primes.push_back(i);
                // 除尽当前的质因子 i
                while (target % i == 0) {
                    target /= i;
                }
            }
        }
        // 如果 target > 1，说明剩下的 target 本身就是一个质因数
        if (target > 1) {
            primes.push_back(target);
        }

        bool flag = true;
        // 遍历 p-1 的所有质因数 q
        for (int q : primes) {
            // 计算指数 (p-1)/q
            int tmp = (p - 1) / q;
            // 检查 a^((p-1)/q) % p 是否等于 1
            // 如果等于 1，说明存在更小的指数使得同余 1 成立，违反原根定义
            if (power_mod(a, tmp, p) == 1) {
                flag = false;
                break;
            }
        }

        if (flag) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }

    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
GESP, 五级
GESP C++ 数论
本文由作者按照 CC BY-NC-SA 4.0 进行授权