求解方法： 枚举
从2开始枚举，然后暴力判断g^(P-1) = 1 (mod P)是否当且当指数为P-1的时候第一次成立
而由于原根一般都不大大多都在200以内，所以可以暴力得到. 方法
例如求任何一个质数x的任何一个原根，一般就是枚举2到x-1，并检验。有一个方便的方法就是，求出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的原根。
原来的复杂度是O(P-1)，现在变成O(m)*log（P-1）m为x-1质因子的个数。质因子的个数也是log级别的。 证明
若存在，那么显然不是原根。
否则，假设存在一个最小的t < phi(x)=x-1使得a^t = 1 (mod x)
那么t一定整除于x-1。
为什么呢？我们假设t不整除于x-1，那么因为t < x-1，所以一定能得到一组k，p，使得x-1 = k * t+p。因为a^t = 1 (mod x)，所以a^（k * t） = 1 (mod x)，又因为a^（x-1） = 1 (mod x)，所以a^p = 1 (mod x)，而p < t 所以t不是最小的，矛盾。
所以那么t一定整除于x-1。所以我们只需要判断x-1的所有因数就行了。我们考虑，t一定是比x-1少一些质因子。而如果a^t = 1 (mod x) 则a^（k*t） = 1 (mod x)。所以我们分解x-1的质因数只要a^（（x-1）/pi ）！=1（mod x）那么所有不包含pi这个质因子的t就不满足a^t = 1 (mod x) 。遍历一遍pi就排除了所有的t。 void divi(int n){//分解质因数 top = 0; for(register int i=1; prim[i]*prim[i]<=n; i++) if(n % prim[i] == 0){ num[++top] = prim[i]; while(n % prim[i] == 0) n /= prim[i]; } if(n != 1) num[++top] = n;// } int root(int p){//求原根 (阶=phi(mod)) divi(p - 1); for(int g=1; ; g++){//枚举原根 bool flag = true; for(int i=1; i<=top; i++){ int goal = (p-1) / num[i]; if(mpow(g, goal, p) == 1) {//check flag = false; break; } } if(flag) return g; } return -1; }