Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Solution
如果我们考虑每个gcd的贡献
那么k作为约数的贡献就是k*phi(n/k)
于是只需要枚举约数计算phi就行了
然而这好像是暴力=v=
然而约数也不可能很多
这么打也非常快
另：从这里也可以推出Σ[d|n]φ(d)=n
考虑phi函数计算
感觉可以考虑pi的贡献
然而我并是理不太清于是弃疗了
官方题解的确是这样：http://www.cnblogs.com/JS-Shining/archive/2012/05/14/2500661.html
各种专有名词云云感觉真要是遇到了也就只能凭感觉蒙一蒙了
Code
枚举约数的技巧是只枚举到sqrt(n)，大约数可由小约数得到
一般phi计算sqrt(n)，搞出素数表可以更快
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std; ll n,ans; ll phi(ll x){
ll ret=x;
for(ll i=;i*i<=x;i++)
if(x%i==){
ret=(ret/i*(i-));
while(x%i==) x/=i;
}
if(x>) ret=ret/x*(x-);
return ret;
} int main(){
scanf("%lld",&n);
for(ll i=;i*i<=n;i++)
if(n%i==){
ans+=i*phi(n/i);
if(i*i<n) ans+=(n/i)*phi(i);
}
printf("%lld\n",ans);
return ;
}