数论知识

欧拉函数，线性素数筛，分解质因数。
  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 }