给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 6

1,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15

 

Input

1个数N(N <= 10^9)

Output

公约数之和

Input示例

6

Output示例

15 ————————————————————————— 这道题枚举 约数d 约数的贡献就是

   $\sum_{d|n}\phi(\frac{n}{d})d$

　因为和n的最大公约数是d的 除以d之后就一定是和n/d 互质的

#include
       
        #include
        
         #include
         
          #define LL long longusing namespace std;int v,n,h[2507],cnt;LL ans;LL f(int x){    for(int i=1;i<=cnt;i++)if(x%h[i]==0)x=x/h[i]*(h[i]-1);    return x;}int main(){    scanf("%d",&n); v=n;    for(int i=2;i*i<=v;i++)if(v%i==0){        h[++cnt]=i;        while(v%i==0) v=v/i;    }    if(v!=1) h[++cnt]=v;     for(int i=1;i*i<=n;i++)if(n%i==0){        int j=n/i;        ans+=f(i)*j;        if(i!=j) ans+=f(j)*i;    }printf("%lld\n",ans);    return 0;}