标签：欧拉函数，数论
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。
分析：
对于gcd(I,N)，设x为N的约数
∑gcd(I,N)=∑phi(N/x)*x
求phi的时候要用O（√n）的算法
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
#define rep(i,a,b) for(LL i=a;i<=b;i++)
#define dep(i,a,b) for(LL i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
long long n,ans,m;
LL phi(LL x)
{
LL t=x;
rep(i,2,m)
if(x%i==0){
t=t/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)t=t/x*(x-1);
return t;
}
int main()
{
cin>>n;
m=sqrt(n);
rep(i,1,m)
if(n%i==0){
ans+=i*phi(n/i);
if(i*i<n)ans+=(n/i)*phi(i);
}
cout<<ans<<endl;
return 0;
}
