A28390. 原根判断
填空题
困难
知识点
题目描述
原根判断
题目描述
小 A 知道，对于质数p而言，p的原根g是满足以下条件的正整数：
- 1<g<p；
- gp-1mod p=1；
- 对于任意1≤i＜p-1均有gp-1mod p≠1 。
其中a mod p表示a除以p的余数。
小 A 现在有一个整数a，请你帮他判断a是不是p的原根。
输入格式
第一行，一个正整数T，表示测试数据组数。
每组测试数据包含一行，两个正整数a,p。
输出格式
对于每组测试数据，输出一行，如果a是p的原根则输出 Yes ，否则输出 No 。
样例
输入样例 1
3
3 998244353
5 998244353
7 998244353输出样例 1
Yes
Yes
No数据范围
对于40% 的测试点，保证3≤p≤103 。
对于所有测试点，保证1≤T≤20 ，3≤p≤109 ，1＜a＜p ，p为质数。
参考答案
#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;
}
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;
}
上一题
下一题