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。
———————————————————————
这道题如果一个数x gcd(n,x)==y 那么gcd(b/y,x/y)==1
所以我们枚举因数d 求一下1-n/d有多少个数和n/d的gcd为1 这个可以用欧拉函数
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
const int M=1e3+;
LL read(){
LL ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
LL n,v,ans;
int p[M],cnt;
LL f(LL x){for(int i=;i<=cnt;i++)if(x%p[i]==) x=x/p[i]*(p[i]-); return x;}
int main(){
n=read(); v=n;
for(LL x=;x*x<=v;x++)if(v%x==){
p[++cnt]=x;
while(v%x==) v/=x;
}
if(v!=) p[++cnt]=v;
for(LL x=;x*x<=n;x++)if(n%x==){
LL y=n/x;
ans=ans+y*f(x);
if(x!=y) ans=ans+x*f(y);
}printf("%lld\n",ans);
return ;
}