原根

2019-04-13 14:41发布

站内文章 / 模拟电子
16704 0 1108
定义：设，，使得成立的最小的，称为对模的阶，记为。
定理：如果模有原根，那么它一共有个原根。
定理：若，，，则。
定理：如果为素数，那么素数一定存在原根，并且模的原根的个数为。
定理：设是正整数，是整数，若模的阶等于，则称为模的一个原根。
   假设一个数对于模来说是原根，那么的结果两两不同,且有，那么可以称为是模的一个原根，归根到底就是当且仅当指数为的时候成立。（这里是素数）
模有原根的充要条件：，其中是奇素数。  
求模素数原根的方法：对素因子分解，即是的标准分解式，若恒有
          
成立，则就是的原根。（对于合数求原根，只需把换成即可）
#include #include #include #include #include #include using namespace std; typedef long long LL; const int N = 1000010; bitset prime; int p[N],pri[N]; int k,cnt; void isprime() { prime.set(); for(int i=2; i 1) pri[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 P; isprime(); while(cin>>P) { Divide(P-1); for(int g=2; g