Primitive Roots POJ

Primitive Roots

原根~
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 #define ll long long
 6 const int maxn = 65536+10;
 7 
 8 int phi[maxn];
 9 
10 void init(){
11     memset(phi,0,sizeof(phi));
12     phi[1] = 1;
13     for(int i = 2; i < maxn; i++) if(!phi[i]) {
14         for(int j = i; j < maxn; j += i) {
15             if(!phi[j]) phi[j] = j;
16             phi[j] = phi[j]/i*(i-1);
17         }
18     }
19 }
20 int main(){
21     int n;
22     init();
23     while(scanf("%d", &n)!=EOF) {
24         printf("%d
",phi[phi[n]]);
25     }
26 }
View Code