Description
Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数，为N。
Output
一个整数，为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。
遇到数论题又跪了....
应该是属于简单题
由于N<=2^32 所以可以用用sqrt(n)的时间枚举它的约数
设gcd(n,m)=k 那么 gcd(n/k,m)=1
phi(n/k)就是满足gcd(n/k,m)=1中m的个数
所以对于确定的约束K，它对答案的贡献为 phi(n/k)*k
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
int phi(ll x)
{ ll i=2; ll ans=x;
while (i*i<=x)
{if (x%i==0)
{ans=ans*(i-1)/i;
while (x%i==0) x=x/i;}
i++;}
if (x>1) ans=ans*(x-1)/x; return ans;
}
int main()
{ ll n;
scanf("%lld",&n);
ll i=1; ll ans=0;
while (i*i<=n)
{if (n%i==0)
{ int a=i; int b=n/i;
if (a!=b)
ans=ans+a*phi(b)+b*phi(a);
else ans=ans+a*phi(b);
}
i++;
}
printf("%lld
",ans);
}