定义（并没有什么用）

阶：设m>1,(a,m)=1,使得a^r=1(modn)成立的最小r，称为a对模m的阶。
原根：原根是一种数学符号，设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）——百度百科

原根的性质

g^1 mod m,g^2 mod m….g^(n-1) mod m都不同，并且答案恰好[1,m-1]一个答案一幂。 mod m有原根的充要条件是：m=2,4,p^a,2*p^a（为素奇数） 如果m有原根，那么原根个数是φ(φ(m))（φ是欧拉函数）

求原根的方法

对φ(p)进行素因此分解，若恒有g^(φ(p)/pi) mod p!=1,则g是p的原根(用欧拉定理和裴蜀定理证的，并不想知道怎么证明QAQ)。 φ(p)在p是素数的时候答案是p-1。 原根没有什么快的方法，只有从2到g-1快速枚举，好在一般原根都不大。 放个题吧：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135 懒得单独求欧拉函数了，直接用p-1，题目给得是素数 #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int maxn=100; int p[maxn]; int fenJie(int n,int *p)//将n进行质因数分解，存在数组p中，返回质因数个数 { int m=sqrt(n+0.5),ret=0; for(int i=2;i<=m;i++) { if(n%i==0) { p[++ret]=i; while(n%i==0)n/=i; m=sqrt(n+0.5); } } if(n)p[++ret]=n; return ret; } int qkpow(int a,int p,int mod)//快速幂 { LL t=1,tt=a%mod; while(p) { if(p&1)t=t*tt%mod; tt=tt*tt%mod; p>>=1; } return t; } int get_G(int x) { bool ok=1; int t=fenJie(x,p),fi=x-1; t=fenJie(fi,p);//分解欧拉函数 for(int g=2;g1; for(int i=1;i<=t;i++) { if(qkpow(g,fi/p[i],x)==1) { ok=0; break; } } if(ok) return g; } return -1; } int main() { int x; scanf("%d",&x); printf("%d ",get_G(x)); return 0; }

作用

有些定理和原根有关系，但是不太需要用到计算哎。 我见过的用处就是NTT需要用嘛，可以预先算出原根来。