GESP C++
5级
真题
202503-原根判断(luogu-P11961)

202503-原根判断(luogu-P11961)

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

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

题目要求

题目背景

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

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

题目描述

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

  • 1<g<p1<g<p；
  • gp−1 mod p=1g^{p-1}\bmod{p}=1；
  • 对于任意 1≤i<p−11\le i<p-1 均有 gi mod p≠1g^i\bmod{p}\neq1。

其中 a mod pa\bmod{p} 表示 aa 除以 pp 的余数。

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1 
3
3 998244353
5 998244353
7 998244353
输出 #1 
Yes
Yes
No

说明/提示

数据范围

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

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

题目分析

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

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

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

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

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

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

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

  • 21≡22^1 \equiv 2
  • 22≡42^2 \equiv 4
  • 23≡12^3 \equiv 1 👉 **注意：**这里 232^3 就已经是 1 了。
  • 因为 3<63 < 6，它提前回到了 1。所以 2 不是 7 的原根。

再检查 a=3a=3：

  • 31≡33^1 \equiv 3
  • 32≡23^2 \equiv 2
  • 33≡63^3 \equiv 6
  • 34≡43^4 \equiv 4
  • 35≡53^5 \equiv 5
  • 36≡13^6 \equiv 1 👉 只有到了最后一步 p−1=6p-1=6 才等于 1。
  • 中间没有提前回到 1，所以 3 是 7 的原根。

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

暴力做法（会超时）

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

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

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

数论优化做法（正解）

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

更进一步，经过推导可以得出判定原根的充要条件： 对于 p−1p-1 的每一个质因数 qq，如果都满足：

ap−1q mod p≠1a^{\frac{p-1}{q}} \bmod p \neq 1

那么 aa 就是原根。

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

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

3. 算法步骤

为了判断 aa 是否为 pp 的原根，我们需要做三件事：

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

示例代码 

#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;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

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

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

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

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于
202503-平均分配(luogu-P11960)202506-奖品兑换(luogu-P13013)