hdu2824 欧拉函数入门题及欧拉函数性质总结_一叶之修的博客

欧拉函数 O(sqrt(n)) 

int Euler(int n){
    int ans = n;

    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            ans = ans/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        ans = ans/n*(n-1);

    return ans;
}int Euler(int n){
    int an