题解：https://blog.csdn.net/tenkuo/article/details/149862986?sharetype=blogdetail&sharerId=149862986&sharerefer=PC&sharesource=tenkuo&spm=1011.2480.3001.8118

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
typedef long long LL;
int prime[N], pr, phi[N];
//prime存质数，pr代表现在筛出来了几个质数，phi存欧拉函数 
LL sp[N]; //欧拉函数前缀和 
bool v[N];
void init(){
	pr=0; phi[1]=1; //欧拉函数初始化，1就是 1 
	memset(v, 0, sizeof(v));
	for(int i=2; i<=N; i++)
	{
		if(v[i]==0) prime[++pr]=i, phi[i]=i-1;
		for(int j=1; (j<=pr)&&(i*prime[j]<=N-10); j++)
		{
			v[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else{
				phi[i*prime[j]]=phi[i]*(prime[j]-1);                          
			}
		}
	}
	sp[0]=0;
	for(int i=1; i<=N-10; i++) sp[i]=sp[i-1]+phi[i];
} 
LL solve(LL x){
	LL res=0;
	for(LL i=1, j; i<=x; i=j+1){
		j=x/(x/i);
		//分块加速 x/i都一样的 i分成一块，一块块的计算
		//这里 j是 x/j=x/i 中的最大的 j 
		res+=(sp[j]-sp[i-1])*(2*sp[x/i]-1);
	}
	return res;
}
int main(){
	init();
	int T; scanf("%d", &T); while(T--){
		LL n; scanf("%lld",&n);
		printf("%lld\n", solve(n));
	}
	return 0;
}