4679: 【GESP2503五级】原根判断
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
输入
第一行，一个正整数 ，表示测试数据组数。
每组测试数据包含一行，两个正整数$a,p$ 。
每组测试数据包含一行，两个正整数$a,p$ 。
输出
对于每组测试数据，输出一行，如果$a$ 是$p$ 的原根则输出
Yes ，否则输出 No 。
样例输入 复制
3
3 998244353
5 998244353
7 998244353样例输出 复制
Yes
Yes
No提示
#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;
}