原根

· · 个人记录

我超，原

阶

我们要先介绍阶。

若(a,m)=1，且x是满足a^x\equiv 1(\bmod m)的最小正整数，我们称x是a\bmod m的阶，简记为ord_ma或\delta_ma。

阶有一些性质：

  1. 若a^y\equiv 1(\mod m)，ord_ma|y，特别地ord_ma|\phi(m)

其他性质不常用。

原根

若(a,m)=1，且ord_ma=\phi(m)，我们称a是m的一个原根。

一般不讨论1的原根。

原根一般有多个。

原根存在定理：m存在原根，当且仅当m为2,4,2p^k,p^k，其中p为奇素数。

若存在原根，个数为\phi(\phi(m))。

原根判定定理：若存在原根，且(a,m)=1，a是m原根的充要条件是，对于\phi(m)的每个质因子p，都有a^{\phi(m)/p}\not\equiv1(\bmod m)。

若有了最小的原根g，那么所有的原根是g^k\bmod m,(k,\phi(m))=1。

王元同志（对就是那个数学竞赛书上的人）证明了，g小于O(m^{0.25})。

所以我们可以用原根判定定理暴力找最小原根，然后不断乘方得到所有原根。

P6091 【模板】原根

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
const int MAXN=1e6+5;
int n,T;
int prm[MAXN>>1],cnt,vis[MAXN],phi[MAXN];
int cnt2,tmp[MAXN];
int cnt3,ans[MAXN];
void sie(){
    phi[1]=1;
    rep(i,2,1e6){
        if(!vis[i])prm[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&i*prm[j]<=1e6;j++){
            vis[i*prm[j]]=1;
            if(i%prm[j]==0){phi[i*prm[j]]=phi[i]*prm[j];break;}
            phi[i*prm[j]]=phi[prm[j]]*phi[i];
        }
    }
}
int ck(int x){
    if(x==2||x==4)return 1;
    if(x%2==0)x>>=1;
    for(int i=2;prm[i]<=x;i++){
        if(x%prm[i]==0){
            while(x%prm[i]==0)x/=prm[i];
            return x==1;
        }
    }
    return 0;
}
void fac(int x){
    cnt2=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            tmp[++cnt2]=i;
            while(x%i==0)x/=i;
        }
    }
    if(x>1)tmp[++cnt2]=x;
}
int gcd(int x,int y){
    return (y==0)?x:gcd(y,x%y);
}
int ksm(int a,int e,int mod){
    int res=1;
    while(e){
        if(e&1)res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        e>>=1;
    }
    return res;
}
int main(){
    sie();
    read(T);
    int d;
    while(T--){
        read(n),read(d);
        if(!ck(n))puts("0\n");
        else{
            fac(phi[n]);
            int g;
            for(int i=1;;i++){
                int ok=1;
                if(gcd(i,n)>1)continue;
                rep(j,1,cnt2)
                    if(ksm(i,phi[n]/tmp[j],n)==1){ok=0;break;}
                if(ok){g=i;break;}
            }
            int t=1;
            cnt3=0;
            for(int i=1;cnt3<phi[phi[n]];i++){
                t=1LL*t*g%n;
                if(gcd(phi[n],i)==1)ans[++cnt3]=t;
            }
            sort(ans+1,ans+cnt3+1);
            printf("%d\n",phi[phi[n]]);
            rep(i,1,cnt3/d)printf("%d ",ans[i*d]);
            puts("");
        }
    }
    return 0;
}

实际应用有NTT，单位根反演等，甚至有的时候可以把数表示为原根的幂次，把加法化为乘法巧解问题。

[ABC212G] Power Pair

即求

\sum_{i=0}^{P-1}\sum_{j=0}^{P-1}[\exists n\in N^{*},i^n\equiv j(\mod P)]

考虑i=0 orj=0，只有i=0,j=0一种情况，所以即求

1+\sum_{i=1}^{P-1}\sum_{j=1}^{P-1}[\exists n\in N^{*},i^n\equiv j(\mod P)]

我们可以用原根g表示1,2,...,\phi(p))，设i=g^a,j=g^b

即求

1+\sum_{i=1}^{P-1}\sum_{j=1}^{P-1}[\exists n\in N^{*},g^{an}\equiv g^{b}(\mod P)]

根据费马小定理，必有循环节\phi(P)

1+\sum_{i=1}^{P-1}\sum_{j=1}^{P-1}[\exists n\in N^{*},an\equiv {b}(\mod P-1)]

我们可以假定n存在时，对b计数。

1+\sum_{i=1}^{P-1}\frac{[a,P-1]}{a} $1+\sum_{i=1}^{P-1}\frac{P-1}{(a,P-1)} 1+\sum_{i|P-1}^{P-1}\frac{P-1}{i}\phi(\frac {P-1}i)

考虑\phi的实际意义即可。

所以答案为1+\sum_{i|P-1}^{P-1}i\phi(i)

可以直接枚举因数，暴力算\phi，可以过。

#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    x*=f;
}
typedef long long ll;
const ll mod=998244353;
ll p;
ll phi(ll n){
    ll res=n,ed=sqrt(n);
    rep(i,2,ed){
        if(n%i==0){
            res=res/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)res=res/n*(n-1);
    return res%mod;
}
int main(){
    read(p);
    p--;
    ll ed=sqrt(p);
    ll ans=1;
    rep(i,1,ed){
        if(p%i!=0)continue;
        ans=(ans+phi(i)*(i%mod)%mod)%mod;
        if(i*i!=p)ans=(ans+phi(p/i)*((p/i)%mod)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}