传送门

题意：
设f(n) = \sum\limits_i^n\sum\limits_j^n\phi(gcd(i,j))，给定T<=5000组询问，每次n<=1e9

将公式化简可以得到(省略反演步骤)

ans = \sum\limits_p\sum\limits_{p|d}\mu(\frac{d}{p})\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor\phi(p)
ans = \sum\limits_p\sum\limits_{d=1}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\phi(p)

此时将内层整除移动到外层，设dp = T

ans = \sum\limits_T\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)

设h(T) = \sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)，想办法处理这个函数的前缀和，与前面整除分块一起计算

观察到这是莫比乌斯函数和欧拉函数的迪利克雷卷积，所以h也是一个积性函数。既然是积性函数，那么可由若互质的因子的函数值相乘得到。

考虑h(pri^x)其中pri为T的一个质因子，x为质因子的个数。由于莫比乌斯函数的自变量只要有两个以上的相同质因子，函数值就为零。观察上面的卷积式子。那么只有当p = pri^x和p = pri^{x-1}的时候，\mu分别为1和-1。即此时\frac{T}{p}=1,\frac{T}{p}=p。所以
h(pri^x) = \phi(pri^x) – \phi(pri^{x-1})

此时就可以线筛了。

线筛的方法如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 233;
int st[maxn];
ll primes[maxn], f[maxn], h[maxn], phi[maxn], low[maxn], cnt;
void get_primes(ll n)
{
    f[1] = 1; phi[1] = 1; low[1] = st[1] = 1;
    for(ll i = 2; i <= n; i++)
    {
        if(!st[i]) low[i] = primes[cnt++] = i, phi[i] = i - 1, f[i] = phi[i] - 1;
        for(int j = 0; j < cnt && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = 1;
            if(i % primes[j] == 0)
            {
                low[i * primes[j]] = low[i] * primes[j];
                phi[i * primes[j]] = phi[i] * primes[j];
                if(low[i] == i) f[i * primes[j]] = phi[i * primes[j]] - phi[i];
                else f[i * primes[j]] = f[i / low[i]] * f[low[i] * primes[j]];
                break; 
            }
            low[i * primes[j]] = primes[j];
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            f[i * primes[j]] = f[i] * (phi[primes[j]] - 1);
        }
    }
    for(int i = 1; i <= n; i++) h[i] = f[i] + h[i - 1];
}
int main()
{
    int T; cin >> T;
    get_primes(10000010);
    //for(int i = 1; i <= 10; i++) cout << f[i] << ' '; puts(" ");
    //for(int i = 1; i <= 10; i++) cout << h[i] << ' '; puts(" ");
    while(T--)
    {
        ll n; 
        scanf("%lld", &n);
        //n = T;
        ll c = 0, ans = 0;
        for(ll i = 1; i <= n; i = c + 1)
        {
            c = n / (n / i);
            ans = ans + (h[c] - h[i - 1]) * ((n / i) * (n / i));
        }
        printf("%lld\n", ans);
    }    
}