原根

单求原根个数phi[phi[n]].

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 const int maxn = 1e5;
 9 bool flag[maxn]; //标记数组
10 ll phi[maxn]; //欧拉函数值
11 int prime[maxn]; //同时得到素数筛
12 int cnt = 0;
13 void Get_phi(int n)
14 {
15     cnt = 0;
16     memset(flag,true,sizeof(flag));
17     phi[1] = 1;
18     for(int i=2;i<=n;i++)
19     {
20         if(flag[i]) //素数
21         {
22             prime[cnt++] = i;
23             phi[i] = i-1; //素数的欧拉函数值是i-1
24         }
25         for(int j=0;j<cnt;j++)
26         {
27             if(i*prime[j]>n)
28             {
29                 break;
30             }
31             flag[i*prime[j]] = false;//素数的倍数不是素数
32             if(i%prime[j]==0) //i%mod prime = 0,那么phi(i*p) = p*phi(i)
33             {
34                 phi[i*prime[j]] = prime[j]*phi[i];
35                 break;
36             }
37             else phi[i*prime[j]] = (prime[j]-1)*phi[i];//i mod prime != 0, 那么 phi(i * prime) == phi(i) * (prime-1)
38         }
39     }
40 }
41 int main()
42 {
43     ll n;
44     Get_phi(maxn-10);
45     while(cin>>n)
46     {
47         cout<<phi[phi[n]]<<endl;
48     }
49     return 0;

求具体原根，一步一步来。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cmath>
  6 using namespace std;
  7 typedef long long ll;
  8 const int maxn = 1e5;
  9 //欧拉函数
 10 ll euler(ll n){ //返回euler(n)
 11      ll res=n,a=n;
 12      for(ll i=2;i*i<=a;i++){
 13          if(a%i==0){
 14              res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
 15              while(a%i==0) a/=i;
 16          }
 17      }
 18      if(a>1) res=res/a*(a-1);
 19      return res;
 20 }
 21 //线性素数筛
 22 int prime[maxn] = {0},num_prime = 0;
 23 int isNotPrime[maxn] = {1,1};
 24 void is_prime(int N)
 25 {
 26     for(int i=2;i<N;i++)
 27     {
 28         if(!isNotPrime[i])
 29         {
 30             prime[num_prime++] = i;
 31         }
 32         for(int j=0;j<num_prime&&i*prime[j]<N;j++)
 33         {
 34             isNotPrime[i*prime[j]] = 1;
 35             if(!(i%prime[j]))
 36             {
 37                 break;
 38             }
 39         }
 40     }
 41     return;
 42 }
 43 //分解质因数
 44 int curprime[maxn];
 45 int cnt = 0;
 46 void dividep(int n)
 47 {
 48     int t = sqrt(1.0*n);
 49     for(int i=0;prime[i]<=t;i++)
 50     {
 51         if(n%prime[i]==0)
 52         {
 53             curprime[cnt++] = prime[i];
 54             while(n%prime[i]==0) n /= prime[i];
 55         }
 56     }
 57     if(n>1) curprime[cnt++] = n;
 58 }
 59 int quick_pow(int a,int n,int mod)
 60 {
 61     int res = 1;
 62     while(n)
 63     {
 64         if(n&1) res = res*a%mod;
 65         n /= 2;
 66         a = a*a%mod;
 67     }
 68     return res;
 69 }
 70 int main()
 71 {
 72     ll n;
 73     is_prime(maxn-10);
 74     /*for(int i=0;i<num_prime;i++)
 75     {
 76         printf("%d ",prime[i]);
 77         if(num_prime%10==0)
 78         {
 79             printf("
");
 80         }
 81     }*/
 82     while(cin>>n)
 83     {
 84         cnt = 0;
 85         dividep(n-1);
 86         int ans = 0;
 87         for(int i=2;i<n;i++)
 88         {
 89             int flag = 0;
 90             for(int j=0;j<cnt;j++)
 91             {
 92                 int t = (n-1)/curprime[j];
 93                 if(quick_pow(i,t,n)==1)
 94                 {
 95                     flag = 1;
 96                     break;
 97                 }
 98             }
 99             if(!flag)
100             {
101                 ans++;
102             }
103         }
104         cout<<ans<<endl;
105     }
106     return 0;
107 }