莫反是不可能莫反的，这辈子都不可能莫反了
题目要求的是
[sumlimits_{i=1}^n sumlimits_{j=i+1}^n gcd(i,j)
]
稍微变个亚子
[sumlimits_{i=1}^n sumlimits_{j=1}^{i-1} gcd(i,j)
]
考虑求(f(n)=sumlimits_{i=1}^{n-1} gcd(n,i))
首先(gcd(n,i) mid n)，考虑枚举(gcd)的值
[f(n)=sumlimits_{d mid n} d sumlimits_{i=1}^{n-1} [gcd(n,i)=d]
]
(gcd(n,i)=d)等价于(gcd(frac{n}{d},frac{i}{d})=1)，于是
[egin{aligned}
f(n)&=sumlimits_{d mid n} d sumlimits_{i=1}^{n-1} [gcd(frac{n}{d},frac{i}{d})=1] \
&=sumlimits_{d mid n} d imes varphi(frac{n}{d})
end{aligned}
]
特别的，(varphi(1)=0)。
筛出欧拉函数，然后类似埃氏筛的枚举(d)，更新(d)的倍数的(f)就好了。
对于(n)，(Ans_n=sumlimits_{i=1}^n f(i))，维护前缀和就好了
跑的超慢的(Code:) 为什么你们那么快啊...
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<(b);i++)
#define per(i,a,b) for (int i=(a)-1;i>=(b);i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
const int maxn=4e6,N=maxn+10;
ll f[N],phi[N],vis[N];
int p[N],pn;
void getphi(int n) {
rep(i,2,n+1) {
if(!vis[i]) {
p[pn++]=i;
phi[i]=i-1;
}
for(int j=0;j<pn&&i*p[j]<=n;j++) {
vis[i*p[j]]=1;
if(i%p[j]==0) {phi[i*p[j]]=phi[i]*p[j];break;}
else phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
void init() {
getphi(maxn);
rep(i,1,maxn+1) for(int j=i*2;j<=maxn;j+=i)
f[j]+=i*phi[j/i];
rep(i,1,maxn+1) f[i]+=f[i-1];
}
int n;
int main() {
init();
while(scanf("%d",&n)==1&&n) printf("%lld
",f[n]);
return 0;
}