简答题 偏难
#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】

3
3 998244353
5 998244353
7 998244353

【样例输出1】

Yes
Yes
No

【数据范围】

对于 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 &lt;cstdio&gt; using namespace std; int a, p; int ans; int fpw(int b, int e) {     if (e == 0)         return 1;     int r = fpw(b, e &gt;&gt; 1);     r = 1ll * r * r % p;     if (e &amp; 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", &amp;T);     while (T--) {         scanf("%d%d", &amp;a, &amp;p);         ans = 1;         int phi = p - 1, r = phi;         for (int i = 2; i * i &lt;= phi; i++)             if (phi % i == 0) {                 check(phi / i);                 while (r % i == 0)                     r /= i;             }         if (r &gt; 1)             check(phi / r);         printf(ans ? "Yes\n" : "No\n");     }     return 0; }</pre>
这道题暂未补解析。