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
       
        #include
        
         #include
         
          #define LL long longconst int M=1e3+7;LL read(){    LL ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
     if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}LL n,v,ans;int p[M],cnt;LL f(LL x){
      for(int i=1;i<=cnt;i++)if(x%p[i]==0) x=x/p[i]*(p[i]-1); return x;}int main(){    n=read(); v=n;    for(LL x=2;x*x<=v;x++)if(v%x==0){        p[++cnt]=x;        while(v%x==0) v/=x;    }    if(v!=1) p[++cnt]=v;    for(LL x=1;x*x<=n;x++)if(n%x==0){        LL y=n/x;        ans=ans+y*f(x);        if(x!=y) ans=ans+x*f(y);    }printf("%lld\n",ans);    return 0;}