Longge's problem[欧拉函数]

​​传送门​​

---

#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
LL n; LL phi(LL x){
LL ans=x;
for(LL i=2;i*i<=x;i++){
if(x%i==0){
ans = (ans/i) * (i-1);
while(x%i==0) x/=i;
}
}if(x>1) ans = (ans/x) * (x-1);
return ans;
}
int main(){
while(~scanf("%lld",&n)){
LL ans=0;
for(LL i=1;i*i<=n;i++){
if(n%i==0){
ans += (LL)phi(n/i)*i;
if(i*i < n) ans += (LL)phi(i)*(n/i);
}
}printf("%lld\n",ans);
}return 0;
}