简答题
偏难
#20484
原根判断 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数: 其中 a mod…
原根判断
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 知道,对于质数 p 而言,p 的原根 g 是满足以下条件的正整数:
其中 a mod p 表示 a 除以 p 的余数。
小 A 现在有一个整数 T,请你帮他判断 a 是不是 p 的原根。
【输入描述】
第一行,一个正整数 T,表示测试数据组数。
每组测试数据包含一行,两个正整数 a、p。
【输出描述】
对于每组测试数据,输出一行,如果 a 是 p 的原根则输出 Yes ,否则输出 No 。
【样例输入1】
【样例输出1】
【数据范围】
对于 40% 的测试点,保证 3<=p<=1000。
对于所有测试点,保证 1<=T<=20, 3<=p<=10^9,1<a<p , p为质数。
对于所有测试点,保证 ,-100<= A(i,j) <=100 。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。