#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=70000;
__int64 phi[maxn];
int main()
{
    int n,i,j;
    for(i=1;i<=maxn;i++)
     phi[i]=i;
    for(i=2;i<=maxn;i+=2)
      phi[i]/=2;
     for(i=3;i<=maxn;i+=2)
       if(phi[i]==i)
         for(j=i;j<=maxn;j+=i)
             phi[j]=phi[j]/i*(i-1);
    while(cin>>n){
        cout<<phi[n-1]<<endl;
    }
    return 0;
}

• Re:为什么单独求欧拉函数就对了，用递推求欧拉函数就RE了呢？ (10) jk10171101 2012-07-11 15:17:25