给定一个整数$N$,求$\sum_{1\le i \le N} \gcd(i,N)$

第一反应大概是这里面会有很多重复的,$qwq$

我们打一下表看看，当$n=20$时

1 2 1 4 5 2 1 4 1 10 1 4 1 2 5 4 1 2 1 20

我们发现这里出现的数只能是$n$的约数（废话）

显然$1$的个数是$\varphi(n)$

我们来考虑一下怎么求$2$的数量

$ \gcd(i,n)=2 $

$\gcd(i/2,n/2)=1$

问题又变成和上面求$1$一样的了，显然答案就是$\varphi(\frac{n}{2})$

所有最终答案就是$\sum_{d \mid n}d*\varphi (\frac{n}{d})$

/*
@ author:pyyyyyy
-----思路------

-----debug-------

*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int phi(int x)
{
    int ret=x;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            ret=ret/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) ret=ret/x*(x-1);
    return ret;
}
int ans;
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i*i<=n;++i)
    { 
        if(n%i==0) {
            ans+=i*phi(n/i);    
            if(i!=n/i) ans+=(n/i)*phi(i);
        }
    }
    cout<<ans;
    return 0;
}