题解：P11961 [GESP202503 五级] 原根判断

Fall_Dream · 2025-03-24 22:22:31 · 题解

普及组选手表示不需要什么费马小定理，只需要快速幂即可（？）\ 首先，显然的，a^{xy} = (a^x) ^y。然后可以假设其中 a^x\equiv 1\pmod p，则有 a^{xy}=(a^x)^y\equiv 1 ^ y\equiv1\pmod p。所以我们可以 O(\sqrt{p}) 分解 p-1 的质因数，然后检查 p-1 的每一个因数 f 是否满足 a^f\equiv 1\pmod p，如果有任意一个因数满足上述条件，直接输出 No。如果所有因数均不满足，输出 Yes。总复杂度 O(T \sqrt{p}\log p)。

代码不刻意压 25 行

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int qpow(int a,int b,int p){
    int res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1,a=a*a%p;
    }
    return res;
}
void solve(){
    int a,p;
    cin>>a>>p;
    for(int i=2;i<=sqrt(p-1);i++)
        if((p-1)%i==0)
            if(qpow(a,i,p)==1||qpow(a,(p-1)/i,p)==1){
                puts("No");return;
            }
    puts("Yes");
}
signed main(){
    int T;cin>>T;
    while(T--) solve();
}