OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

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

📅 2025-11-22·✍️ OneCoder·计算中...·⏱️ 11 分钟

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

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

题目要求

题目背景

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

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

题目描述

小 A 知道,对于质数 而言, 的原根 是满足以下条件的正整数:

  • ;
  • ;
  • 对于任意 均有 。

其中 表示 除以 的余数。

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1
PLAINTEXT4 行
3
3 998244353
5 998244353
7 998244353
输出 #1
PLAINTEXT3 行
Yes
Yes
No

说明/提示

数据范围

对于 的测试点,保证 。

对于所有测试点,保证 ,,, 为质数。


题目分析

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

1. 通俗理解:什么是“原根”?

题目中给了三个条件,我们来翻译一下。假设模数 是一个质数(比如 )。

  • 条件 1: 。(这只是限制 的范围,输入保证了,不用管)
  • 条件 2: 。(根据费马小定理,只要 是质数且 不是 的倍数,这个条件恒成立,所以也不用特意检查)
  • 条件 3(核心): 对于任意 ,都有 。

通俗解释: 你可以把 看作一个发电机,它通过不断地自乘()在模 的世界里生成数字。

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

举个例子 (): 我们要检查 是不是原根。我们需要看 到 。

  • 👉 **注意:**这里 就已经是 1 了。
  • 因为 ,它提前回到了 1。所以 2 不是 7 的原根。

再检查 :

  • 👉 只有到了最后一步 才等于 1。
  • 中间没有提前回到 1,所以 3 是 7 的原根。

2. 解题思路:如何快速判断?

暴力做法(会超时)

最直接的想法是写一个循环,从 到 ,挨个计算 ,看是否等于 1。

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

问题: 最大是 。如果你循环 次,程序会跑好几秒甚至超时(计算机一秒大概跑 次)。

数论优化做法(正解)

我们需要用到一个数学结论: 如果 会“提前”回到 1,那么它回到 1 的步数(指数)一定是 的约数。

更进一步,经过推导可以得出判定原根的充要条件: 对于 的每一个质因数 ,如果都满足: 那么 就是原根。

只要有一个质因数 使得 ,那么 就不是原根。

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

3. 算法步骤

为了判断 是否为 的原根,我们需要做三件事:

  1. 计算 。
  2. 对 进行质因数分解。
    • 找出 的所有不同的质因子 。
    • 例如:如果 ,则 ,质因子是 2 和 3。
    • 例如:如果 ,则 ,唯一的质因子是 2。
  3. 进行快速幂检测。(这部分算法,后续详细介绍,常用算法)
    • 对于每一个质因子 ,计算 。
    • 如果发现某个 ,说明它“提前”回到了 1,判定失败 (No)。
    • 如果所有质因子测试完,都没有出现 1,判定成功 (Yes)。

示例代码

C++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;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!