P6091 【模板】原根

· · 题解

前置知识:

阶

定义：

满足同余式子 a^n\equiv1(\bmod {m}) 的最小正整数 n 存在，就称 n 为 a 模 m 的阶，记作 \ \delta_m(a)。

性质：

  2. 若 a^n\equiv1\ (\bmod \ m) ，则 \delta_m(a)\ \mid\ n。

  3. 设 m \in \mathbf{N}^+ \ \ a,b \in \mathbf{Z},\gcd(a,m)=\gcd(b,m)=1， 有 \delta_m(a,b)=\delta_m(a)\times\delta_m(b)\ 的充分必要条件是\ \gcd(\delta_m(a),\delta_m(b))=1。

  4. 设 k\in \mathbf{N}^\ \ m\in \mathbf{N}^+,a\in \mathbf{Z},\gcd(a,m)=1，则 \delta_m(a^k)= \frac{ \delta_m(a) }{\gcd(\delta_m(a),k)}。

原根

定义：

若 m\in\mathbf{N}^+,g \in \mathbf{Z}，\gcd(g,m)=1，且 \delta_m(g)=\phi(m)，则称 g 为模 m 的原根。

存在定理：

一个数 m 存在原根当且仅当 m=2,4,p^a,2p^a, p 为奇素数，a\in \mathbf{N}^+。

判定定理：

设 m \geq 3，且 \gcd(m,g)=1，则 g 为模 m 的原根的充分必要条件是： 对于 \phi(m) 的每个素因子 p，都有

g^{\ \frac{\phi(m)}{p} } \ \not\equiv 1(\bmod m)

原根个数：

若一个数有原根，则它的原根的个数为 \phi(\phi(m))，

如对证明感兴趣可以去 oi wiki 上查看关于阶和原根及其定理的证明 ，取自 oi wiki。

扩充：

若 a,m 互质，a^{\phi(m)}\equiv\ 1(\bmod\ m) ，由于在模 m 的意义下，因为 a^{\phi(m+1)} 又回到了 a^1。所以 a^1,a^2\cdot\cdot\cdot\cdot 这样的序列将有一个长度为 \phi(m) 的循环节， 我们把最短循环节的长度定义为 a 在模 m 下的阶 (\delta_m(a))。

题意及主要思路：

题目很简单，就是求数 n 的所有原根，通过原根判断定理，我们可以先求出最小原根，因为其满足原根判断定理，设模 m 意义下有原根，枚举 \phi(m) 以内的正整数 g^x，并且 \gcd(x,\ \phi(m))=1，以此求出所有原根。

求解步骤：

1.初始化值域范围内的欧拉函数（线性筛） 时间复杂度 O(n)。

2.通过原根存在定理判断是否存在原根。

3.通过求出 \phi(m) 的所有素因子，设为 j，通过原根定义找出与 m 互质的数 s，再通过原根判断定理判断枚举的 s 是否符合 s^{ \tfrac{\phi(m)}{j}}\not\equiv\ 1\ (\bmod\ m)。

4.通过最小原根找出所有原根。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int phi[N],prime[N];
bool st[N];
int cnt,T;
vector<int>q,ans;

void euler_phi(int n){//初始化欧拉函数 
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

LL ksm(LL a,int b,int p){//用来找最小原根 
    LL res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

void cut_prime(int n){//分解数的欧拉函数用于找最小原根 
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            q.push_back(i);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)q.push_back(n);
}

bool pd(int n){
    if(n==2||n==4)return true;
    if(n%2==0)n/=2;
    for(int i=2;prime[i]<=n;i++){//若有原根则有唯一的质数分解 
        if(n%prime[i]==0){
            while(n%prime[i]==0)n/=prime[i];
            return n==1;
        }
    }
    return false;
}

int main(){
    euler_phi(N);//初始化所有数的欧拉函数 
    cin>>T;
    for(int i=1;i<=T;i++){
        int n,d;scanf("%d%d",&n,&d);
        if(pd(n)){
            q.clear();ans.clear();
            cut_prime(phi[n]);
            int need;LL last=1;//指数 
            for(int k=1;;k++){
                bool flag=true;
                if(__gcd(k,n)!=1)continue;
                for(int j=0;j<q.size();j++){
                    if(ksm(k,phi[n]/q[j],n)==1){
                        flag=false;
                        break;
                    }
                }
                if(flag){
                    need=k;//最小原根 
                    break;
                }
            }
            for(int k=1;ans.size()<phi[phi[n]];k++){
                last=last*need%n;
                if(__gcd(phi[n],k)==1)ans.push_back(last);
            }
            sort(ans.begin(),ans.end());
            printf("%d\n",phi[phi[n]]);//原根个数
            for(int k=d-1;k<phi[phi[n]]/d*d && k<ans.size();k+=d){
                printf("%d ",ans[k]);
            } 
            cout<<endl;
        } 
        else puts("0\n");
    }
    return 0;
}