题目大意：有$T(Tleqslant 3 imes 10^5)$组数据，每组数据给你$n(nleqslant 10^6)$，求$displaystylesumlimits_{i=1}^n [i,n]$（$[a,b]$表示$a$和$b$的$LCM$）
题解：
$$
defdsum{displaystylesumlimits}
egin{align*}
dsum_{i=1}^n[i,n]&=dsum_{i=1}^n dfrac{icdot n}{(i,n)}\
&=ndsum_{d|n}dsum_{i|n\d|i}dfrac{i}{d}cdot[(i,n)==d]（d为枚举的gcd）\
&=ndsum_{d|n}dsum_{i=1}^{frac{n}{d}}icdot[(i,dfrac{n}{d})==1]（i为是d的几倍）\
end{align*}\
$$
$$
defdsum{displaystylesumlimits}
重点在如何求dsum_{i=1}^{frac{n}{d}}icdot[(i,dfrac{n}{d})==1]\
先令m=dfrac{n}{d}\
dsum_{i=1}^m i[(i,m)==1]\
也就是求dsum_{(i,m)==1}i\
发现若(d,m)==1且m
eq 1Rightarrow(m-d,m)==1\
herefore dsum_{(i,m)==1}i=
egin{cases}
&dfrac{mvarphi(m)}{2}&(m
eq 1)\
&1&(m==1)
end{cases}\
为了避免麻烦，下面令varphi(1)=2\
则dsum_{(i,m)==1}i=dfrac{mvarphi(m)}{2}\
hereforedsum_{i=1}^n[i,n]=ndsum_{d|n}dfrac{dfrac{n}{d}varphiig(dfrac{n}{d}ig)}{2}\
令f(i)=dsum_{d|i}dfrac{dfrac{i}{d}varphiig(dfrac{i}{d}ig)}{2}\
就可以O(1)求出答案了
$$
卡点：1.线性求$varphi$的时候判断条件求错
C++ Code：
#include <cstdio>
#define maxn 1000010
using namespace std;
int Tim, n;
int phi[maxn], plist[maxn], ptot;
long long f[maxn];
bool isp[maxn];
void sieve(int n) {
phi[1] = 2;
for (int i = 2; i < n; i++) {
if (!isp[i]) plist[ptot++] = i, phi[i] = i - 1;
for (int j = 0; j < ptot && i * plist[j] < n; j++) {
int tmp = i * plist[j];
isp[tmp] = true;
if (i % plist[j] == 0) {
phi[tmp] = phi[i] * plist[j];
break;
}
phi[tmp] = phi[i] * phi[plist[j]];
}
}
for (int i= 1; i < n; i++) {
long long tmp = 1ll * i * phi[i] >> 1;
for (int j = i; j < n; j += i) f[j] += tmp;
}
}
int main() {
sieve(maxn);
scanf("%d", &Tim);
while (Tim --> 0) {
scanf("%d", &n);
printf("%lld
", f[n] * n);
}
return 0;
}