[模板]原根-学习笔记

退役选手学IO啦... 我太笨了，竟然忘了埃氏筛怎么写（要从$i^2$开始循环），但是记得线性筛怎么写...可能这就是肌肉记忆吧。 [Learn from this](https://www.luogu.com.cn/blog/11DBeyonder/solution-p6091) 关于原根的一些小知识： ## 阶 设 $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)$。 ```cpp 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(); } ```