题解： 原根判断

· · 题解

题目背景

截止 2025 年 3 月，本题可能超出了 GESP 考纲范围。在该时间点下，原根是 NOI 大纲 8 级知识点（NOI 级），且不属于 GESP 大纲内容。需要注意，GESP 大纲和 NOI 大纲是不同的大纲。 若对题目中原根这一概念感兴趣，可以学习完成 【模板】原根。

~本萌新只是个五年级刚学oi的蒟蒻，本想考个五级，结果qwq……我的两道编程题都ac了 \(^v^)/~

题意：

对于质数 p 而言，p 的原根 g 是满足以下条件的正整数：

其中 a\bmod{p} 表示 a 除以 p 的余数。

给出一个整数 a 和质数 p，判断 a 是不是 p 的原根。

保证 1\le T\le20，3\le p\le10^9，1<a<p，p 为质数。

思路：

要想让 a 是 p 的原根，必须满足三个条件：

  3. 对于任意 1\le i<p-1 均有 a^i\bmod{p}\neq1，如何判断？

枚举每个 i，依次用快速幂判断，但还是慢了。

正难则反，只需要知道 a^i\bmod{p}=1 的结果，就知道 a^i\bmod{p}\neq1。

在 [1,p-1) 中，那个 i 可能满足 a^i\bmod{p}=1?

假设 a^k\bmod{p}=1。

\therefore\\a^{k}\bmod p=1,\\\\a^{k+1}\bmod{p}=a,\\a^{k+2}\bmod{p}=a^2\bmod p,\\\dots\\a^{2k}\bmod p=1,\\\dots\\a^{3k}\bmod p=1,\\\dots\\a^{xk}\bmod p=1 \quad x\in[0,\infty]

wow，有周期，每 k 个一循环，每个循环周期大小相等！

因为 a^{p-1}\bmod{p}\not=1 我们提前判段为错误，并退出了，所以现在的 a 和 p 一定满足 a^{p-1}\bmod{p}=1。

诶，我们忽略了 0，a^0 \bmod p=1！

也就是说我们要将 1 到 p-1 划分成若干段长度相同的循环周期，在 [1,p-1) 中，只有每小段的末尾，也就是 p-1 的因数的倍数，可能满足 a^i\bmod{p}=1。

又知道 p-1 的一个因数 x，使得 a^x\bmod{p}=1，那么，这个因数的任意一个倍数 y，也都满足 a^y\bmod{p}=1。

所以只用找 p-1 的每一个因数 x 是否满足 a^x\bmod{p}=1，就可以推出"对于任意 1\le i<p-1 均有 a^i\bmod{p}\neq1"这个条件了

代码（含注释）：

//c++
#include<iostream>
#include<vector>
#define ll long long
using namespace std;
vector<ll>yin;       //表示p-1的因数
ll fpow(ll a,ll b,ll p){//快速幂
    a%=p;
    if(b==1)return a;
    if(b==0)return 1;
    if(b&1)return a*fpow(a*a%p,(b>>1),p)%p;
    return fpow(a*a%p,(b>>1),p);
}
void find_yin(ll x){    //找因数
    while(yin.size())   //清空
        yin.pop_back();    
    for(ll i=2;i*i<=x;i++){
        if(x%i==0){
            yin.push_back(i);
            yin.push_back(x/i);
        }
    }
    return ;
}
void doing(){//求出每次答案
    ll p,a;
    cin>>a>>p;
    if(fpow(a,p-1,p)!=1){  //条件2
        puts("No");
        return ;
    }
    find_yin(p-1);         //找p-1的因数
    for(int i=0;i<yin.size();i++){
        ll y=yin[i];       //枚举每个因数
        if(fpow(a,y,p)==1){//满足条件4(不满足条件3)
            puts("No");
            return ;
        }
    }
    puts("Yes");
    return ;
}
int main(){
    int t; 
    cin>>t;
    while(t--){
        doing();
    }
    return 0;
}

复杂度：