1 /*  2 POJ2480 Longge's problem  3 http://poj.org/problem?id=2480  4 数论 欧拉函数 线性筛   5   6 求sigma_i=1^n{gcd(i,n)}  7 <=>sigma_d|n{d*phi(n/d)}  8  *  9  * 10  * 11  * 12  */ 13 #include 
     
       14 #include 
      
        15 #include 
       
         16 #define new 17 #ifdef OLD 18 //250ms 19 using namespace std; 20 const long long Nmax=1000005LL; 21 long long n; 22 int is_prime[Nmax]; 23 int prime[Nmax]; 24 int cnt; 25 long long phi[Nmax]; 26 long long oula(long long n) 27 { 28     if(n==1LL) 29         return 1LL; 30     if(n
        
         1LL) ret*=n-1LL; 42     return ret; 43 } 44  45 void get() 46 { 47     for(int i=2;i
         
          =Nmax) 59                 break; 60             is_prime[i*prime[j]]=0; 61             if(i%prime[j]==0) 62             { 63                 phi[i*prime[j]]=phi[i]*(long long)prime[j]; 64                 break; 65             } 66             else 67                 phi[i*prime[j]]=phi[i]*(long long)(prime[j]-1); 68         } 69     } 70 } 71  72 int main() 73 { 74     // freopen("1.in","r",stdin); 75     //scanf("%lld%lld",&a,&b); 76     //printf("%lld\n",gcd(a,b)); 77     get(); 78     while(scanf("%lld",&n)==1) 79     { 80         //n=read(); 81         //printf("%lld\n",n); 82         //if(n==0LL) 83             //break; 84         if(n