class="markdown_views prism-dracula">

1.定义

原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。
——百度

---

阶的定义：
若gcd（a,p）=1，则最小的正整数n使得an≡1(mod p)" role="presentation" style="position: relative;">an≡1(mod p)$a^n\equiv 1(modp)$为a模p的阶（而且一定存在这样一个阶）
性质：
设gcd（a,p）=1 ，a模p的阶为n. 若正整数N使得aN≡1(mod p)" role="presentation" style="position: relative;">aN≡1(mod p)$a^N\equiv 1(modp)$, 则 n∣N
设gcd（a,p）=1 ，a模p的阶n整除φ（p）

---

原根好像有性质
对于正整数m，只有当m=2，4，pa" role="presentation" style="position: relative;">pa$p^a$，2∗pa" role="presentation" style="position: relative;">2∗pa$2\ast p^a$时m才有原根（p为奇素数，a≥1）
所以可以特判啦
然后呢对于m的原根g，满足gi(mod p)" role="presentation" style="position: relative;">gi(mod p)$g^i(modp)$（0<=i<=p-2）与1到p-1一一对应

2.求原根

---

暴力求法
求m的原根时，因为原根一般都比较小，那么就从2开始枚举g，只需要判断g模m的阶是否是φ(m)就好了，怎么判呢，枚举每个数i（1<=i<φ(m)）算gi≡1(modm)" role="presentation" style="position: relative;">gi≡1(modm)$g^i\equiv 1(modm)$若满足则这个g一定不是原根
代码 #include #include inline int phi(int n) { int zc=n,all=sqrt(n); for(int i=2;i<=all;i++) { if(n%i!=0)continue; zc=zc/i*(i-1); while(n%i==0)n/=i; } if(n>1)zc=zc/n*(n-1); return zc; } inline int pow(int x,const int y,const int mod) { int res=1; for(int i=1;i<=y;i<<=1,x=x*x%mod)if(i&y)res=res*x%mod; return res; } inline int G(const int m) { const int PHI=phi(m); for(int g=2;;g++) { bool fla=1; if(pow(g,PHI,m)!=1)continue; for(int i=1;iif(pow(g,i,m)==1) { fla=0; break; } if(fla)return g; } } int m,g; int main() { scanf("%d",&m); g=G(m); printf("%d",g); return 0; } 复杂度？
φ(m)*log(m)*O(g)
这个算法在m为大质数的时候根本跑不过

---

稍快的算法
容易发现，我们在枚举g的时候只要枚举与m互质的数，若不互质，那么一定不满足一一对应的条件
不过很多情况下我们要求的都是一个质数的原根，所以这个优化不常用
代码略

---

更快的算法
在上面的代码中，容易发现，枚举的i并不是每个每个都有用的，有一个结论，枚举i只需要枚举φ(m)的因数就好了
为什么呢，那么现在就是已知对于所有b(b|φ(m))" role="presentation" style="position: relative;">b(b|φ(m))$b(b|\phi (m))$都不满足gb≡1(mod m)" role="presentation" style="position: relative;">gb≡1(mod m)$g^b\equiv 1(modm)$，求证对于所有b（b不满足b|φ(m)" role="presentation" style="position: relative;">b|φ(m)$b|\phi (m)$且1<=b<φ(m)" role="presentation" style="position: relative;">1<=b<φ(m)$1<=b<\phi (m)$），也不会满足gb≡1(mod m)" role="presentation" style="position: relative;">gb≡1(mod m)$g^b\equiv 1(modm)$
证明：
由欧拉定理可知gφ(m)≡1(mod m)" role="presentation" style="position: relative;">gφ(m)≡1(mod m)$g^{\phi (m)}\equiv 1(modm)$
然后使用反证法，设有合法的b满足gb≡1(mod m)" role="presentation" style="position: relative;">gb≡1(mod m)$g^b\equiv 1(modm)$（根据已知得出b|φ(m)" role="presentation" style="position: relative;">b|φ(m)$b|\phi (m)$不成立）
设这些存在的b中的最小值为c1" role="presentation" style="position: relative;">c1$c_1$，即那么gc1≡1(mod m)" role="presentation" style="position: relative;">gc1≡1(mod m)$g^{c_1}\equiv 1(modm)$
设c2=φ(m)−c1" role="presentation" style="position: relative;">c2=φ(m)−c1$c_2=\phi (m)-c_1$
那么gc2≡1(mod m)" role="presentation" style="position: relative;">gc2≡1(mod m)$g^{c_2}\equiv 1(modm)$
所以满足c2>=c1" role="presentation" style="position: relative;">c2>=c1$c_2>=c_1$
若c1|c2" role="presentation" style="position: relative;">c1|c2$c_1|c_2$那么设c2=a∗c1" role="presentation" style="position: relative;">c2=a∗c1$c_2=a\ast c_1$(a为整数)
因为φ(m)=c1+c2=(a+1)∗c1" role="presentation" style="position: relative;">