GESP认证C++编程真题解析 | P11961 [GESP202503 五级] 原根判断

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

【题目来源】

洛谷：P11961 [GESP202503 五级] 原根判断 - 洛谷 (luogu.com.cn)

【题目描述】

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

• 1 < g < p 1<g<p1<g<p；
• g p − 1 m o d p = 1 g^{p−1}\ mod\ p=1gp−1modp=1；
• 对于任意1 ≤ i < p − 1 1≤i<p−11≤i<p−1均有g i m o d p = 1 g^i\ mod\ p=1gimodp=1。

其中a m o d p a\ mod\ pamodp表示a aa除以p pp的余数。

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

【输入】

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

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

【输出】

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

【输入样例】

3 3 998244353 5 998244353 7 998244353

【输出样例】

Yes Yes No

【算法标签】

《洛谷 P11961 原根判断》 #原根# #数论# #欧拉函数# #GESP# #2025#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 定义宏，将int替换为long long类型intT;// 测试用例的数量// 快速幂函数，计算a^b mod pintqmi(inta,intb,intp){intres=1;// 初始化结果为1while(b){// 当指数b不为0时循环if(b&1)// 如果b的最低位为1res=res*a%p;// 将当前a乘入结果a=a*a%p;// a自乘b>>=1;// b右移一位}returnres;// 返回结果}signedmain(){// 使用signed代替int，因为宏定义了int为long longcin>>T;// 输入测试用例数量Twhile(T--){// 处理每个测试用例inta,p;cin>>a>>p;// 输入a和p// 检查费马小定理是否成立：a^(p-1) ≡ 1 mod pif(qmi(a,p-1,p)!=1){cout<<"No"<<endl;// 不成立则直接输出Nocontinue;}boolflag=true;// 标记是否为原根// 检查p-1的所有真因子i，判断a^i ≡ 1 mod p是否成立for(inti=2;i*i<=p-1;i++){if((p-1)%i)continue;// 跳过不是p-1的因子的i// 如果a^i ≡ 1 mod p或a^((p-1)/i) ≡ 1 mod p，则a不是原根if(qmi(a,i,p)==1||qmi(a,(p-1)/i,p)==1){flag=false;// 标记为不是原根break;// 提前退出循环}}// 根据flag输出结果if(flag)cout<<"Yes"<<endl;// 是原根elsecout<<"No"<<endl;// 不是原根}return0;}

【运行结果】

3 3 998244353 Yes 5 998244353 Yes 7 998244353 No