题解 P6091 【【模板】原根】

· · 题解

【模板】原根

有一些我不太会证明的结论，希望之后有人在题解区能证一下...

首先，什么样的数才有原根？

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

怎么求一个数 n 的所有原根？

首先找到 n 的最小原根，设为 g，则 n 的所有原根可以由 g 的若干次乘方得到。

具体地，若 n 存在原根，则其原根个数为 \varphi(\varphi(n))，每一个原根都形如 g^k 的形式，要求满足 \gcd(k,\varphi(n))=1。

于是，我们在得到 n 的最小原根 g 后便可在 O(\varphi(n)\log \varphi(n)) 的时间复杂度内得到 n 的所有原根。

如何得到 n 的最小原根？

枚举即可。从小到大枚举 g 并检验是否是 n 的原根（我听说 n 的最小原根是 O(n^{0.25}) 级别的，不太确定对不对）。检验的方法如下：

根据原根的定义，如果 g 是 n 的原根，除了满足 g^{\varphi(n)}\equiv 1 外，还需要满足对于任意更小的 k 有 g^k\ne 1。而我们不可能把小于 \varphi(n) 的所有数都拿出来检验。

事实上，关于阶有一条强的性质：如果 \gcd(a,n)=1，且 a^k\equiv 1\bmod n，则 k|\varphi(n)，所以我们事实上只需要检验 \varphi(n) 的所有真因子即可，进一步地，设 n 的所有素因数为 p_1,\ldots,p_l，则只需要检验所有的 \dfrac{\varphi(n)}{p_i} 即可，因为他们涵盖了 \varphi(n) 所有真因子的倍数。

于是我们可以在 O(n^{0.25}\log n) 的复杂度内得到 n 的最小原根，进而计算所有原根。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int t,p,cnt,tot,ctans,fc[MAXN],ans[MAXN],pri[MAXN],rt[MAXN],q[MAXN],phi[MAXN];
void init () {
    phi[1]=1;
    for (int i=2;i<=MAXN-10;i++) {
        if (!q[i]) {pri[++tot]=i,phi[i]=i-1;}
        for (int j=1;j<=tot&&pri[j]*i<=MAXN-10;j++) {
            q[i*pri[j]]=1;
            if (i%pri[j]==0) {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    }
    rt[2]=rt[4]=1;
    for (int i=2;i<=tot;i++) {
        for (int j=1;(1ll*j*pri[i])<=MAXN-10;j*=pri[i]) {rt[j*pri[i]]=1;}
        for (int j=2;(1ll*j*pri[i])<=MAXN-10;j*=pri[i]) {rt[j*pri[i]]=1;}
    }
    return;
}
int gcd (int a,int b) {return (b==0?a:gcd(b,a%b));}
int qpow (int a,int b,int p) {
    int res=1;
    while (b) {
        if (b&1) {res=(1ll*res*a)%p;}
        a=(1ll*a*a)%p;
        b>>=1;
    }
    return res;
}
void proc (int p) {
    for (int i=2;i*i<=p;i++) {
        if (p%i==0) {
            fc[++cnt]=i;
            while (p%i==0) {p/=i;}
        }
    }
    if (p>1) {fc[++cnt]=p;}
    return;
}
bool chk (int x,int p) {
    if (qpow(x,phi[p],p)!=1) {return 0;}
    for (int i=1;i<=cnt;i++) {
        if (qpow(x,phi[p]/fc[i],p)==1) {return 0;}
    }
    return 1;
}
int findrt (int p) {
    for (int i=1;i<p;i++) {
        if (chk(i,p)) {return i;}
    }
    return 0;
}
void getrt (int p,int x) {
    int prod=1;
    for (int i=1;i<=phi[p];i++) {
        prod=(1ll*prod*x)%p;
        if (gcd(i,phi[p])==1) {
            ans[++ctans]=prod;
        }
    }
    return;
}
int main () {
    init();
    scanf("%d",&t);
    for (int ii=1;ii<=t;ii++) {
        int wtf;
        scanf("%d%d",&p,&wtf);
        if (rt[p]) {
            ctans=cnt=0;
            proc(phi[p]);
            int mn=findrt(p);
            getrt(p,mn);
            sort(ans+1,ans+ctans+1);
            printf("%d\n",ctans); 
            for (int i=1;i<=ctans/wtf;i++) {printf("%d ",ans[i*wtf]);}
            printf("\n");
        } else {
            printf("0\n\n");
        }
    }
    return 0;
}