好像是可以A掉的哎（牛半仙的妹子gcd）

经过本蒟蒻的百般打表与观察，大致得出如下结论：

我们应该按照1~n每个数来分n个类。

我神奇地发现了欧拉函数十分有用。

欧拉函数：

由此，每一个数都可以来分类，而我们要找求的是三个数的最大公约数，所以我们应该在的基础上再乘上，于是再把他们加起来就可以了。

所以，code就是——

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

int main() {
    int n, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int t = i, i1 = i;
        for (int j = 2; j * j <= i1; j++) {
            if (i1 % j == 0) {
                t = t / j * (j - 1);
                while (i1 % j == 0) i1 /= j;
            }
        }
        if (i1 > 1) t = t / i1 * (i1 - 1);
        ans += t * (n / i) * (n / i) * (n / i);
    }
    cout << ans << endl;
    return 0;
} 

总的来说，时间复杂度降到了

总算低于啦！