原根

2019-04-13 13:40发布

站内文章 / 模拟电子
13724 0 1683
 定义：设，，使得成立的最小的，称为对模的阶，记为。
定理：如果模有原根，那么它一共有个原根。
定理：若，，，则。
定理：如果为素数，那么素数一定存在原根，并且模的原根的个数为。
定理：设是正整数，是整数，若模的阶等于，则称为模的一个原根。
   假设一个数对于模来说是原根，那么的结果两两不同,且有，那么可以称为是模的一个原根，归根到底就是当且仅当指数为的时候成立。（这里是素数）
模有原根的充要条件：，其中是奇素数。  
求模素数原根的方法：对素因子分解，即是的标准分解式，若恒有
          
成立，则就是的原根。（对于合数求原根，只需把换成即可） /********************* 求一个数的原根 (一)p是一个质数 p-1 = p1^a1*p1*a2*...*pk^ak; 对于所有的pi都有g^((p-1)/pi)!=1(mod p); 那么g是模p的一个原根 (二) p是一个合数 将p-1改成phi(p)就行了。 **********************/ #include #include #include using namespace std; const int maxn = 50010; typedef long long LL; int p[maxn],cnt; void divide(int n){ cnt=0; for(int i=2;i*i<=n;i++){ if(n%i==0){ p[cnt++]=i; while(n%i==0) n/=i; } } if(n>1) p[cnt++]=n; } LL quick_mod(LL a,LL b,LL m){ LL ans = 1; a%=m; while(b){ if(b&1){ ans = ans*a%m; b--; } b>>=1; a=a*a%m; } return ans; } int main() { int n; while(~scanf("%lld",&n)){ divide(n-1); for(int i=2;i

热门文章