[模板]原根-学习笔记

退役选手学IO啦...

我太笨了，竟然忘了埃氏筛怎么写（要从i^2开始循环），但是记得线性筛怎么写...可能这就是肌肉记忆吧。

Learn from this

关于原根的一些小知识：

阶

设 a,m\in\mathbb{N^+}，且 a\perp m ，使 a^x\equiv 1\pmod m 成立的最小正整数 x ，称为 a 模 m 的阶，记为 \text{ord}_ma 。

有意思的性质

原根

原根的定义

设 g,m\in\mathbb N^+ ，且 g\bot m ；若 \mathrm{ord}_mg=\varphi(m) ，则称 g 是模 m 的原根。

原根存在定理

模 {\displaystyle m} 有原根的充要条件是 m=2,4,p^k,2p^k ，其中 p 是奇素数， k 是任意正整数。

原根判定定理

若 g 为模 m 的原根，则对于任意 \varphi(m) 的质因子 p ，必有 g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m 。

求所有原根

首先我们要求出最小原根，有性质：最小原根不大于\sqrt[4]{m}级别，所以一点点枚举即可。

求出原根之后，我们再找出与\phi(m)互质的所有数（可以用埃氏筛控制复杂度），这样就能得到所有\varphi(\varphi(m))个原根。

使用基数排序加速。最终复杂度小于O(n\log n)。

const int N=1e6+5;
bitset<N> notp;
int p[N], cntp;
int phi[N];
bitset<N*2> exi;
void shai(int n)
{
    notp[1]=1;
    for(int i=2; i<=n; ++i)
    {
        if(!notp[i])
        {
            p[++cntp]=i;
            phi[i]=i-1;
        }
        for(int j=1, t; j<=cntp&&(t=p[j]*i)<=n; ++j)
        {
            notp[t]=1;
            if(i%p[j]==0)
            {
                phi[t]=phi[i]*p[j];
                break;
            }
            phi[t]=phi[i]*(p[j]-1);
        }
    }
    exi[2]=exi[4]=1;
    for(int i=1; i<=cntp; ++i)
        for(LL j=p[i]; j<=n; j*=p[i])
            exi[j]=1, exi[j<<1]=1;
}
int fac[50], cntf;
bitset<N> notg;
void dofac(int n)
{
    int _n=n;
    for(int i=1; i<=cntp&&p[i]<=n; ++i)
    {
        if(n%p[i]==0)
        {
            int tp=p[i];
            fac[++cntf]=tp;
            while(n%tp==0) n/=tp;
            for(int j=tp; j<=_n; j+=tp) notg[j]=1;
        }
    }
}
int getg(int n)
{
    bool flg;
    for(int i=2;; ++i)
    {
        if(gcd(i, n)!=1) continue;
        flg=1;
        for(int j=1; j<=cntf; ++j)
            if(qpow(i, phi[n]/fac[j], n)==1) {flg=0; break;}
        if(flg) return i;
    }
}
bitset<N> buk;
int v[N], cntv;
void clear()
{
    cntf=cntv=0;
    notg.reset();
    buk.reset();
}
void solve(int n, int d)
{
    if(n==2)
    {
        puts("1");
        puts(d==1?"1":"");
        return;
    }
    if(!exi[n])
    {
        puts("0\n");
        return;
    }
    int m=phi[n];
    dofac(m);
    int g=getg(n);
    for(int i=1; i<m; ++i)
        if(!notg[i])
        {
            buk[qpow(g, i, n)]=1;
        }
    for(int i=1; i<=n; ++i)
        if(buk[i])
        {
            v[++cntv]=i;
        }
    out(cntv);
    for(int i=d; i<=cntv; i+=d) out(v[i], ' ');
    enter;
    clear();
}