记录一道 GESP 2025年3月 的数论真题。这类题在考试里属于必得分项核心就那几行代码关键是别在小细节上丢分。题目来源ACGO A62072 2025年3月 五级赛事场次2025年3月 五级一、题目信息题目名称原根判断赛事场次2025年3月 五级难度定位五级涉及知识点原根 数论题目链接https://www.acgo.cn/problemset/info/62072坑点预警这里最容易失分整除性质同余运算模运算下的加减乘。题意简述小 A 知道对于质数 p 而言p 的原根 g 是满足以下条件的正整数1 g p;gᵖ⁻¹ mod p 1;对于任意 1 ≤ i p - 1 均有 gⁱ mod p ≠ 1。其中 a mod p 表示 a 除以 p 的余数。小 A 现在有一个整数 a请你帮他判断 a 是不是 p 的原根。前置知识下面先把需要的基础知识理一遍不熟悉的朋友可以跟着看熟悉的直接跳过。整数除法与取余C 中两个整数相除结果仍是整数小数部分直接舍去例如5/2得到 2 而不是 2.5。要得到小数必须先把其中一个数转成 double。取余运算a % b得到 a 除以 b 的余数常用来判断整除关系例如n % 2 0表示 n 是偶数。二、思路分析先看清楚题目要我们做什么把题目读两遍我们提取出关键信息输入是什么、要输出什么、有哪些约束条件。这道题考查的是数论属于这类题里比较基础的一道把题目要求一步步翻译成代码逻辑就能解决。我的思考过程读完题之后我的第一反应是这样的# 题解原根判断顺着这个方向往下想就得到完整做法解题思路原根的定义原根 g 必须满足 gᵖ⁻¹ mod p 1。对于所有 1 ≤ i需要说明的是上面这个思路是把题目要求直译成代码得到的没有用到什么高级技巧。对于这类基础题读准题意加写对边界比追求巧妙解法更重要因为考试里这种题是必须拿满分的。三、完整代码 逐行注释#include cstdio using namespace std; int a, p; int ans; // 快速幂函数 int fpw(int b, int e) { if (e 0) // 判断 return 1; int r fpw(b, e 1); r 1LL * r * r % p; if (e 1) // 判断 r 1LL * r * b % p; return r; } // 检查 a^e mod p 是否等于 1 void check(int e) { if (fpw(a, e) 1) // 判断 ans 0; } int main() { int T; scanf(%d, T); while (T--) { scanf(%d%d, a, p); ans 1; int phi p - 1, r phi; // 分解质因数并检查 for (int i 2; i * i phi; i) { // 遍历 if (phi % i 0) { // 判断 check(phi / i); while (r % i 0) r / i; } } if (r 1) // 判断 check(phi / r); // 输出结果 printf(ans ? Yes\n : No\n); } return 0; }四、代码分段拆解代码不长但每一段都有讲究我们分段拆开看。第一步引入头文件#include cstdio using namespace std;#include iostream提供输入输出功能using namespace std;让我们能直接写cin、cout而不用加前缀。这两行是几乎所有 C 程序的开头照写即可。第二步读入数据scanf(%d, T); scanf(%d%d, a, p);注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用long long。第三步核心处理逻辑while (T--) { for (int i 2; i * i phi; i) { while (r % i 0)这一段是整道题的关键也是数论的体现。看循环的三个要素从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错结果都会不对。第四步按要求输出printf(ans ? Yes\n : No\n);输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA这种分丢得最可惜。五、实例模拟光看代码可能还不够直观我们用题目的样例实际跑一遍看看程序是怎么走的。以题目的第一组样例为例样例输入3 3 998244353 5 998244353 7 998244353样例输出Yes Yes No把这份输入代进代码程序会先把数据依次读入然后进入循环逐个判断把满足条件的值累积起来最后按格式输出。建议你对照着代码在纸上走一遍前两次循环确认自己对每一步的理解都和程序一致。六、踩坑总结下面是做这道题时最容易出错的地方对照自己的代码检查一下变量类型选错虽然本题范围不大但养成习惯——凡是不确定范围时累加变量一律用long long成本为零但能保命。取余与整除混淆a % b取的是余数a / b取的是整数商两个完全不同。判断倍数关系用a % b 0写成a / b 0就全错了。循环起点搞错题目说的是「正整数」循环要从 1 开始而不是从 0 开始差一个数就是 WA。输出格式不符题目要求输出几行就输出几行行末换行、数字之间的空格都要严格对齐算法对了但格式错了同样判 WA这种分丢得最冤。特殊情况没特判把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入出题人最喜欢在这里设陷阱。七、知识点拓展最后总结一下这道题带给我们的通用经验本题考查数论的基本写法这类题在考试中属于必得分项要练到能默写。写完代码后建议自己造几组边界数据测试特别是最小值和最大值。同一知识点在不同场次反复出现把这道题的写法吃透后面遇到同类题可以直接套用。八、适用人群适合正在备考 五级、想确认自己数论基础是否扎实的同学。以上就是这道题的全部内容。这个系列会按考试场次逐题更新觉得有帮助的话可以关注一下也欢迎在评论区留下你的解法。