标签：找出 gcd 原根 int varphi now

原根：

原根定义：

\[a^{q}\not\equiv 1\pmod m~~~~~~~~~q,a\in[1,\varphi(m))\cup Z \]

满足上述则a是模m意义下的原根

如何找出最小的原根g呢？

我们从1开始枚举now，如果\(gcd(now,n)\ne1\)那一定不是原根

找出一个可能是原根的数，我们从\([1-\varphi(n))\)枚举每个k判断\(now^k\equiv1\pmod m\)是否成立

如果全都不同余1，那么就找到了g，可以容易的找出其他原根：

    while(++g){
        int now=1,bj=0;
        if(gcd(g,n)!=1) continue;
        for(int j=1;j<phi[n];j++){
            now=now*g%n;
            if(now==1){
                bj=1;
                break;
            }
        }
        if(bj==1) continue;
        else if(bj==0){
            break;
        }
    }

如何找出其他原根

我们认为g是最小的原根

寻找方法：

在\(gcd(k,\varphi(m))\)条件下,\((g^{k})\)也是模m意义下的原根

然后我们来证明这样的寻找方法是正确的

\[\delta_m(g)=\varphi(m) \]

\[\delta_m(g^k)=\frac { \varphi(m)} { gcd(\varphi(m),k) } \]

我们要使得\(\frac {\varphi(m)} {gcd(\varphi(m),k)}=\varphi(m)\)

所以\(gcd(\varphi(m),k)=1\)

代码

    int now=g;
    ans[++cnt]=g;
    for(int j=2;j<phi[n];j++){
        now=now*g%n;
        if(gcd(j,phi[n])!=1) continue;
        ans[++cnt]=now;
    }

如何知道模m意义下有无原根呢？

这些数有原根

\(结论：2,4,p^k,2×p^k，其中 p 为奇素数，k 为正整数。\)

证明详见

原根

如何知道原根数量

我们在前面可以知道，当求出一个g(最小原根)，

在\(gcd(k,\varphi(m))=1\)条件下,\((g^{k})\)也是模m意义下的原根\(~~~k\in[1,\varphi(m))\)

有多少个k满足:\(k\in[1,\varphi(m))~~~gcd(k,\varphi(m))=1\)

其实就是\(\varphi(\varphi(m))\)

总代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int phi[N],prim[N],v[N],vis[N],tot=0,ans[N],cnt=0;
int t,n,d;
void pre(){
    phi[1]=1;
    for(int i=2;i<=N-1;i++){
        if(!v[i]){
            prim[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot&&prim[j]*i<=N-10;j++){
            v[i*prim[j]]=1;
            if(i%prim[j]==0){
                phi[i*prim[j]]=phi[i]*prim[j];
                break;    
            }else{
                phi[i*prim[j]]=phi[i]*phi[prim[j]];
            } 
        }
    }
    vis[2]=1;
    vis[4]=1;
    for(int i=2;i<=tot;i++){
        for(long long j=1;j<=N;j=j*prim[i]){
            if(j>N-10){
                break;    
            }
            vis[j]=1;
            if(2*j<=N-1) vis[2*j]=1;
        }
    }
}//预处理phi和prime
int gcd(int x,int y){
    if(y==0) return x;
    return gcd(y,x%y);
}
void input(){
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        cnt=0;
        memset(ans,0,sizeof(ans));
        scanf("%d%d",&n,&d);
        if(!vis[n]){
            printf("0\n\n");
            continue;    
        }
        int g=0;
        while(++g){
            int now=1,bj=0;
            if(gcd(g,n)!=1) continue;
            for(int j=1;j<phi[n];j++){
                now=now*g%n;
                if(now==1){
                    bj=1;
                    break;
                }
            }
            if(bj==1) continue;
            else if(bj==0){
                break;
            }
        }
        int now=g;
        ans[++cnt]=g;
        for(int j=2;j<phi[n];j++){
            now=now*g%n;
            if(gcd(j,phi[n])!=1) continue;
            ans[++cnt]=now;
        }
        sort(ans+1,ans+1+cnt);
        printf("%d\n",phi[phi[n]]);
        for(int j=1;j<=phi[phi[n]]/d;j++){
            printf("%d ",ans[j*d]);
        }
        printf("\n");

    }
}
int main(){
//     freopen("1.txt","w",stdout);
    pre();
    input();

    return 0;
}

完结撒花~~~~

标签：找出,gcd,原根,int,varphi,now
From： https://www.cnblogs.com/hfjh/p/17056345.html