BZOJ2705 SDOI2012 Longge的问题 欧拉函数

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

const int MAXN=(1<<31);
ll N,ans,M;

int phi(int x){
    ll t=x;
    for(ll i=2;i<=M;i++){
        if(!(x%i)){
            t=t/i*(i-1);
            while(!(x%i)) x/=i;
        }
    }
    if(x>1) t=t/x*(x-1);
    return t;
}

int main(){
    cin >> N,M=sqrt(N);
    for(ll i=1;i<=M;i++)
        if(!(N%i)){
            ans+=i*phi(N/i);
            if(i*i<N) ans+=N/i*phi(i);
        }
    cout << ans << endl;

    return 0;
}