定义：
在mod P 域中，若 (a^i)!=(a^j) (0<=i,j<φ（p）) 则称其a为P的原根。
说人话就是：
如果g是P的原根，那么g的（1…P-1）次幂mod P的结果一定互不相同。
这个很重要，说明 a 是 一个群的生成元
那么我们如何求原根呢?
我们求原根，往往只要找一个就行了，那么我们考虑暴力
首先，原根的数量并不少，P的原根有φ（φ（p））个，我们可以暴力枚举 i（from 2 to p-1）去检查每个i是否合法。
我们发现chenk 要O(P)的时间复杂度，太大了。
有一个方便的方法就是，求出x-1所有不同的质因子p1,p2…pm，对于任何2<=a<=x-1,判定a是否为x的原根，只需要检验a((x-1)/p1),a((x-1)/p2),…a((x-1)/pm)这m个数 中，是否存在一个数mod x为1，若存在，a不是x的原根，否则就是x的原根。
我们定义A为p-1的不同素因子的个数，我们发现其增长速率极慢，比N！的反函数增长还慢，我们可以证明在N<1e18内，p不会超过25，不妨视为常数
那么我们的时间复杂度就达到了
check 原来的复杂度是O(P-1)，现在变成O(25*log（P-1））m为x-1质因子的个数。很明显质因子的个数远远小于x-1。
证明如下：
假设存在一个t < phi(x)=x-1使得at ≡ 1 (mod x)
那么由裴蜀定理，一定存在一组k,r使得kt=(x-1)r+gcd(t,x-1)
而由欧拉定理有，a(x-1) ≡ 1 (mod x)
于是1 ≡ a(kt) ≡ a(xr-r+gcd(t,x-1)) ≡ agcd(t,x-1) (mod x)
而t < x-1故gcd(t,x-1) < x-1
又gcd(t,x-1)|x-1 于是gcd(t,x-1)必整除(x-1)/p1,(x-1)/p2…(x-1)/pm其中至少一个，设其一为(x-1)/pi
那么a((x-1)/pi) ≡ (agcd(t,x-1))s ≡ 1s ≡ 1 (mod x)
这与假设矛盾
练习题：（链接点这里）
#include<bits/stdc++.h> #define N 100007 #define LL long long int p[N]; int l[N>>2],pm[N>>4],tog,tot,mo,x; using namespace std; LL qsm(LL x,LL y) { static LL anw; for(anw=1;y;y>>=1,x=x*x%mo) if(y&1) anw=anw*x%mo; return anw; } void getp(int x){ for (int i=2;i<N;i++) { if (!p[i]) l[++tog]=i; for (int j=1;j<=tog&&i*l[j]<N;j++) { p[i*l[j]]=l[j]; if (i%l[j]==0) break; } } x=x-1; for (int i=1;i<=tog&&l[i]*l[i]<x;i++) if (x%l[i]==0) { pm[++tot]=l[i]; while (x%pm[tot]==0) x/=pm[tot]; } if (x!=1) pm[++tot]=x; } bool check(int x){ for (int i=1;i<=tot;i++) if (qsm(x,(mo-1)/pm[i])==1) return 0; return 1; } int PP(int x){ for (int i=1;i<=x;i++) if (check(i)) return i; } int main () { // freopen("a.in","r",stdin); scanf("%d",&x); getp(x); mo=x; printf("%d ",PP(x)); }