前两篇题解筛素数完全就是画蛇添足啊……
本题答案就是 $$\sum_{d\mid n}\frac{n}{d}\varphi(d)$$ 就不再多说了。
刚开始打了个纯纯的暴力，结果给 T 了，然后看了看题解说要筛素数……于是也被误导了写了个筛素数的……结果最后才发现 T 的原因是溢出了……
A 了之后又仔细想了一下，其实直接算的话复杂度并不是 $O(n)$。
正确的复杂度是什么？考虑枚举 $n$ 的约数复杂度为 $O(\sqrt{n})$，而对于一个约数 $d$，计算其欧拉函数也就是枚举其质因子的复杂度也为 $O(\sqrt{d})$，于是其复杂度的计算式应为 $$\sum_{d|n}\sqrt{d}$$ 可以变换一下，得到 $$\sum_{d|\sqrt{n}} d$$二者虽不是完全等价，但是是同阶的，可以用来分析。于是发现这是一个约数和函数，即 $\sigma(\sqrt{n})$。在这篇文章中，根据引理二，暴力做法的复杂度更加精确的上界应该是 $O(\sqrt{n}\log\sqrt{n})$。考虑到 $n<2^{31}$，本题暴力完全可以通过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int phi(int x)
{
    int ans=x;
    for(int i=2;(ll)i*i<=x;++i)
        if(x%i==0)
        {
            ans=(ll)ans*(i-1)/i;
            while(x%i==0) x/=i;
        }
    if(x>1) ans=(ll)ans*(x-1)/x;
    return ans;
}

int main()
{
    int n; scanf("%d",&n);
    ll ans=0;
    for(int i=1;(ll)i*i<=n;++i)
        if(n%i==0)
        {
            ans+=(n/i)*phi(i);
            if(i*i!=n) ans+=i*phi(n/i);
        }
    printf("%lld",ans);
    return 0;
}

补一句，本题还有一种做法是利用 $\varphi(p^a)=p^a-p^{a-1}$ 求解（其中 $p$ 为质数），但如果不知道这个性质还是写暴力吧……（能过就行