传送门

解法：欧拉函数

俗话说数论上来先打表，打完表智力就正常了

我先打了一张n为50的表
//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
发现gcd好像有很多重复的数字

gcd为1的就是与50互质的数，个数为\phi{(N)}个

gcd为2的个数怎么算？仔细想想，对于每一个gcd(i,N) = d的数对，都存在gcd(i/d , N/d) = 1
也就是说，对于每个数对，各自除以gcd和N都是互质的，那么很明显数对的个数为\phi{(N/d)}

有了以上结论，可以想到，N的所有gcd的可能性就是N的所有约数，对于每个约数，数对的个数为\phi{(N/d)}个，它们的和就是d\phi{(N/d)}。

进一步总结，答案就是\sum_{d|N}d\phi{(N/d)}

这个函数是两个积性函数的迪利克雷卷积，所以是个积性函数，有xxxx的性质，可以线筛等等

然而我一看数据范围2^31那比不可能线筛，只能暴力算了。

但实际上是可以优化的。枚举每一个小于\sqrt{(N)}的约数，都有i和N/i。可以先线筛出1e5以内的质数和欧拉函数。
如果N/i大于1e5，那么算欧拉函数的时候就暴力算，因为提前筛出了质数，所以对暴力算欧拉函数有极大的加速作用。
而对于小于1e5的，直接用线筛出来的欧拉函数值就可以了。

整个算法复杂度应该是根号级别的，实测非常快，40ms。

//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233, N = 1e5;
int primes[maxn], phi[maxn], cnt;
bool st[maxn];
void get_primes(int n)
{
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
        for(int j = 0; j < cnt && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = 1;
            if(i % primes[j] == 0)
            {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
            else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}
int euler(int n)
{
    int ans = n;
    for(int i = 0; i < cnt; i++)
    {
        if(primes[i] * primes[i] > n) break;
        if(n % primes[i] == 0)
        {
            ans = ans / primes[i] * (primes[i] - 1);
            while(n % primes[i] == 0) n /= primes[i];
        }
    }
    if(n > 1) ans = ans / n * (n - 1);
    return ans;
}
int main()
{
    get_primes(N);
    ll n;
    ll ans = 0;
    cin >> n;
    for(int i = 1; (ll)i * i <= n; i++)
    {
        if(n % i == 0)
        {
            int t = n / i;
            if(t < N) ans += i * phi[t];
            else ans += i * euler(t);
            if(i != t)
            {
                ans += t * phi[i];
            }
        }
    }
    //if(n > 1) ans += n * euler(n);
    cout<<ans;
}