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

DFM_O · 2025-03-23 20:58:47 · 题解

P11961 题目

解题思路

由原根的性质，当 p\ge3 时，g 为 p 的原根，当且仅当 \gcd(g,p)=1 且对于所有 \varphi(p) 的质因数 q，都有 g^{\frac{\varphi(p)}{q}}\bmod p\not=1，因为若 \gcd(g,p)\not=1，则 g^{\varphi(p)}\bmod p\not=1。

而对于 g^{\frac{\varphi(p)}{q}}\bmod p\not=1 这个条件，必要性是显然的，下面对于充分性进行证明：若存在一个最小的 i 满足 i<\varphi(p) 且 g^i\bmod p=1，则 i 一定为 \varphi(p) 的因数，又因为 i\not=\varphi(p)，所以一定存在一个 \varphi(p) 的质因数 q，满足 \frac{\varphi(p)}{q} 为 i 的倍数，此时 g^{\frac{\varphi(p)}{q}}\bmod p=1，于是我们便知道，只要对于所有的 \varphi(p) 的质因数 q，都有 g^{\frac{\varphi(p)}{q}}\bmod p\not=1，那么就不会存在 i\in[1,\varphi(p)-1]，满足 g^i\bmod p=1。

在本题中，由于 p 为质数，于是 \varphi(p)=p-1，枚举 p-1 的质因数并检查即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline bool pd(int a)
{
    if(a<2)
        return false;
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)
            return false;
    }
    return true;
}
inline long long poww(long long a,long long b,long long p)
{
    long long ss=1;
    while(b)
    {
        if(b&1)
            ss=ss*a%p;
        a=a*a%p;
        b>>=1;  
    }
    return ss;
}
signed main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int g,p;
        cin>>g>>p;
        int phi=p-1;
        if(__gcd(g,p)!=1)
        {
            cout<<"No\n";
            continue;
        }
        int pdd=0;
        for(int i=1;i<=sqrt(phi);i++)
        {
            if(phi%i==0)
            {
                if(pd(i)==1&&poww(g,phi/i,p)==1||pd(phi/i)==1&&poww(g,i,p==1))
                {
                    pdd=1;
                    break;
                }
            }
        }
        if(pdd==0)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}