题解 P6091 【【模板】原根】

· · 题解

效率更优秀的算法！时间复杂度 O(Tn\log\log\log n) 。

首先，原根是什么以及如何求原根这里就不再赘述了，可以移步其他题解。

求原根的过程大致分为以下5步：

1.线性筛预处理所有质数和有原根的数，O(n) 。

2.将 \varphi(n) 分解因数，由于质数已经筛出，复杂度 O(n^{0.5}/\log n) 。

3.快速幂求出最小原根，复杂度大概是 O(n^{0.25}\log n\log\log n) 。

4.通过最小原根求出所有原根，需要进行 \varphi(n)次求最大公约数， O(n\log n) 。

5.排序，从小到大输出， O(n\log n) 。

很容易看出，复杂度瓶颈是第4步和第5步。

第5步排序很容易优化，用计数排序代替快速排序就可以 O(n) 。

关键是第4步。由于我们要求出所有小于 \varphi(n) 的与 \varphi(n) 互质的数，可以考虑用埃氏筛的思想。第2步中 \varphi(n) 的质因数已经求出，可以用这些数标记所有与 \varphi(n) 不互质的数，复杂度优化至 O(n\log\log\log n) 。

代码如下（不开O2不到1s跑完所有数据，比常规方法快了约10倍）：

#include<cstdio>
const int N=1e6+7;
int pr[N],ph[N],fc[9],u[11],v[11],a[N];
bool f[N],b[N],p[N],q[N];
void init(int n){//第1步线性筛，b数组记录是否有原根
    b[2]=b[4]=ph[1]=1;
    int i,j,k,t=0;
    for(i=2;i<=n;++i){
        if(!f[i])pr[++t]=i,ph[i]=i-1;
        for(j=1;k=i*pr[j],k<=n&&j<=t;++j){
            f[k]=1;
            if(!(i%pr[j])){
                ph[k]=ph[i]*pr[j];
                break;
            }
            ph[k]=ph[i]*ph[pr[j]];
        }
    }
    for(i=2;i<=t;++i){
        for(j=1;j*1ll*pr[i]<=n;b[j*=pr[i]]=1);
        for(j=2;j*1ll*pr[i]<=n;b[j*=pr[i]]=1);
    }
}
int qp(int a,int b,int p){
    int r=1;
    while(b){
        if(b&1)r=r*1ll*a%p;
        a=a*1ll*a%p,b>>=1;
    }
    return r;
}
int main(){
    int T,n=0,m,d,i,j,k,t,o,s;
    scanf("%d",&T);
    for(i=1;i<=T;++i)scanf("%d%d",u+i,v+i),n=n>u[i]?n:u[i];
    init(n);
    for(o=1;o<=T;++o){
        n=u[o],d=v[o];
        if(!b[n]){
            puts("0\n");
            continue;
        }
        for(i=1,j=m=ph[n],t=0;pr[i]*pr[i]<=j;++i){
            if(!(j%pr[i])){
                fc[++t]=s=pr[i];
                do j/=s;while(!(j%s));
                for(k=s;k<=m;k+=s)p[k]=1;
            }
        }//第2步及第4步
        if(j>1){
            fc[++t]=j;
            for(k=j;k<=m;k+=j)p[k]=1;
        }
        for(j=1;;++j){
            while(qp(j,m,n)!=1)++j;
            for(i=1;i<=t&&qp(j,m/fc[i],n)!=1;++i);
            if(i>t)break;
        }//第3步
        for(t=j,i=1,s=0;i<=m;++i,t=t*1ll*j%n)if(!p[i])q[t]=1,++s;else p[i]=0;//第4步中求原根的部分
        printf("%d\n",s);
        for(i=1,j=0;i<n;++i){
            if(q[i]){
                q[i]=0,++j;
                if(j==d)j=0,printf("%d ",i);
            }
        }//第5步
        puts("");
    }
    return 0;
}

upd：其实可以 O(n) 的 ， 但是这样做常数更小 。

可以用这种方法通过 P5285 的第 15 个点 。