原根

2019-04-13 13:48发布

站内文章 / 模拟电子
16415 0 1289
定义：设，，使得成立的最小的，称为对模的阶，记为。
定理：如果模有原根，那么它一共有个原根。
定理：若，，，则。
定理：如果为素数，那么素数一定存在原根，并且模的原根的个数为。
定理：设是正整数，是整数，若模的阶等于，则称为模的一个原根。
   假设一个数对于模来说是原根，那么的结果两两不同,且有，那么可以称为是模的一个原根，归根到底就是当且仅当指数为的时候成立。（这里是素数）
模有原根的充要条件：，其中是奇素数。  
求模素数原根的方法：对素因子分解，即是的标准分解式，若恒有
          
成立，则就是的原根。（对于合数求原根，只需把换成即可）
[cpp] view plain copy
  1. #include   
  2. #include   
  3. #include   
  4. #include   
  5. #include   
  6. #include   
  7.   
  8. using namespace std;  
  9. typedef long long LL;  
  10.   
  11. const int N = 1000010;  
  12.   
  13. bitset prime;  
  14. int p[N],pri[N];  
  15. int k,cnt;  
  16.   
  17. void isprime()  
  18. {  
  19.     prime.set();  
  20.     for(int i=2; i
  21.     {  
  22.         if(prime[i])  
  23.         {  
  24.             p[k++] = i;  
  25.             for(int j=i+i; j
  26.                 prime[j] = false;  
  27.         }  
  28.     }  
  29. }  
  30.   
  31. void Divide(int n)  
  32. {  
  33.     cnt = 0;  
  34.     int t = (int)sqrt(1.0*n);  
  35.     for(int i=0; p[i]<=t; i++)  
  36.     {  
  37.         if(n%p[i]==0)  
  38.         {  
  39.             pri[cnt++] = p[i];  
  40.             while(n%p[i]==0) n /= p[i];  
  41.         }  
  42.     }  
  43.     if(n > 1)  
  44.         pri[cnt++] = n;  
  45. }  
  46.   
  47. LL quick_mod(LL a,LL b,LL m)  
  48. {  
  49.     LL ans = 1;  
  50.     a %= m;  
  51.     while(b)  
  52.     {  
  53.         if(b&1)  
  54.         {  
  55.             ans = ans * a % m;  
  56.             b--;  
  57.         }  
  58.         b >>= 1;  
  59.         a = a * a % m;  
  60.     }  
  61.     return ans;  
  62. }  
  63.   
  64. int main()  
  65. {  
  66.     int P;  
  67.     isprime();  
  68.     while(cin>>P)  
  69.     {  
  70.         Divide(P-1);  
  71.         for(int g=2; g
  72.         {  
  73.             bool flag = true;  
  74.             for(int i=0; i
  75.             {  
  76.                 int t = (P - 1) / pri[i];  
  77.                 if(quick_mod(g,t,P) == 1)  
  78.                 {  
  79.                     flag = false;  
  80.                     break;  
  81.                 }  
  82.             }  
  83.             if(flag)  
  84.             {  
  85.                 int root = g;  
  86.                 cout<
  87.             }  
  88.         }  
  89.     }  
  90.     return 0;  
  91. }  

热门文章