题解：
推式子 ：
枚举\gcd(i, j)
则原式可化为
\sum\limits_{p=1}^{n} \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} \varphi(p)[\gcd(i,j)=p]
我们把\varphi(p)提到前面化为
\sum\limits_{p=1}^{n} \varphi(p)\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n}[\gcd(i,j)=p]
把[\gcd(i,j)=p] 中的p除到前面，则原式可化为
\sum\limits_{p=1}^{n} \varphi(p)\sum\limits_{i=1}^{\lfloor \frac{n}{p}\rfloor} \sum\limits_{j=1}^{\lfloor \frac{n}{p}\rfloor}[\gcd(i,j)=1]
设函数f(n)表示 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=1]
则原式可视为 \sum\limits_{p=1}^{n} \varphi(p)\times f(\lfloor \frac{n}{p}\rfloor)
考虑化简函数f(n)
这个函数和欧拉函数有些相似。
首先我们只考虑i\ge j的情况；
\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i}[\gcd(i,j)=1] => \sum\limits_{i=1}^{n}\varphi(i)
同理，我们发现只考虑i\le j的情况，
也为\sum\limits_{j=1}^{n}\varphi(j)
两种情况同时考虑，i=j的情况重复，去重f(n)最终可化简为2 \times\sum\limits_{i=1}^{n}\varphi(i) -1
综上所述，我们可以发现ans = \sum\limits_{p=1}^{n} \varphi(p) \times 2 \times\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\varphi(i) -1
现在我们有了一个O(n)的方法求解ans 但是数据组数为T = 5000 .
我们需要更加优化的方法才能解决问题。
我们先把S_\varphi处理出来
再把每个答案O(\sqrt n)处理，根号求和。再乘上前面相应的\varphi(p)
故总的时间复杂度为$O(n + T\times \sqrt n)
代码 ：
#include
#include
#include
#define ll long long
using namespace std;
const int N = 10000000;
int phi[N], pr[N];
bool np[N];
ll s[N];
void init() {
s[1] = phi[1] = 1;
for(int i = 2; i < N; i ++ ) {
if(!np[i]) {
pr[++*pr] = i;
phi[i] = i-1;
}
for(int j = 1; j <= *pr && i*pr[j] < N; j ++ ) {
np[i*pr[j]] = 1;
if(i%pr[j] == 0) {
phi[i*pr[j]]=phi[i]*pr[j];
break;
}
else phi[i*pr[j]] = phi[i]*(pr[j]-1);
}
s[i] = s[i-1]+phi[i];
}
}
int main() {
int t;
scanf("%d", &t);
init();
while(t -- ) {
int n; ll ans=0;
scanf("%d", &n);
int lst = 0;
for(int p = 1; p <= n;p = lst+1) {
lst = n/(n/p);
ans += (s[lst]-s[p-1])*(s[n/p]*2-1);
}
printf("%lld\n", ans);
}
}