poj 1284 求原根的个数（欧拉函数的应用）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <stack>
 5 #include <queue>
 6 #include <map>
 7 #include <algorithm>
 8 #include <vector>
 9 
10 using namespace std;
11 
12 const int maxn = 1000005;
13 
14 typedef long long LL;
15 
16 int main()
17 {
18     int n;
19     while(cin>>n){
20         n--;
21         int res = n;
22         for(int i=2;i*i<=n;i++){
23             if(n%i == 0){
24                 res -= res/i;
25                 n /= i;
26 
27             while(n%i==0) n/=i;
28             }
29         }
30         if( n > 1) res -= res/n;
31         printf("%d\n",res);
32     }
33 
34     return 0;
35 }