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

知识点：原根、质因数分解、快速幂。

解题思路

分解素数p的p-1的不同质因子q，用快速幂检查每个a^((p-1)/q) mod p是否均不为1。

为什么正确

a的阶整除p-1；若阶小于p-1，则它整除某个(p-1)/q，故会被至少一个检查发现，反之全通过即为原根。

易错点

此判定利用题目p为素数且a在合法范围内；只需不同质因子，不必重复相同因子。

复杂度

每组O(√p+ω(p-1)log p)，空间O(ω(p-1))。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    auto pw=[](long long a,long long e,long long p) {
        long long z=1;
        while(e) {
            if(e&1)z=z*a%p;
            a=a*a%p;
            e>>=1;
        }
        return z;
    }
    ;
    int t;
    cin>>t;
    while(t--) {
        long long a,p;
        cin>>a>>p;
        long long x=p-1;
        vector<long long>f;
        for(long long q=2;q*q<=x;q++)if(x%q==0) {
            f.push_back(q);
            while(x%q==0)x/=q;
        }
        if(x>1)f.push_back(x);
        bool ok=true;
        for(long long q:f)if(pw(a,(p-1)/q,p)==1)ok=false;
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。