lei/

\[\sum^n_{i = 1} lcm(i,n)=\sum^{n}_{i=1}\frac{in}{gcd(i, n)}= \]
\[\sum^{n}_{d|n}\sum^{n}_{i=1}\frac{in}{d}[gcd(i,n)==d]= \]
\[n \times \sum^{n}_{d|n}\sum^{\frac{n}{d}}_{i=1}i[gcd(i, \frac{n}{d})==1] \]

记\(\sum^{\frac{n}{d}}_{i=1}i[gcd(i, \frac{n}{d})==1]\)为\(f(a)\)

\[sum(a)=\sum^a_{i=1}i[gcd(i,a)==1] \]
\[=\sum^a_{i=1}i\sum_{d|gcd(i,a)}\mu(d) \]
\[=\sum^a_{d=1}\mu(d)\sum^a_{i=1}i[d|a \ and \ d|i] \]
\[=\sum_{d|a}\mu(d)d\sum^{\frac{a}{d}}_{i=1}i \]

后面的那个四个马可以直接计算，然后通过枚举每一个数d的倍数来贡献，从而预处理出\(sum\)数组，复杂度\(O(n\ln n)\)
然后答案就变成

\[n \times \sum^n_{d|n}sum[\frac{n}{d}] \]

和上面一样的操作对每个\(n\)算贡献，加上去好了，复杂度同上。
总复杂度\(O(n \ln n + T)\)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

#define LL long long
#define R register
const int N = 1e6 + 10;
inline int read() {
	int x = 0, f = 1; char a = getchar();
	for(; a > '9' || a < '0'; a = getchar()) if (a == '-') f = -1;
	for(; a >= '0' && a <= '9'; a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

int p[N], tot, mu[N], vis[N];
LL sum[N], f[N];
inline void pre() {
	mu[1] = 1;
	for(R int i = 2; i < N; i ++) {
		if(vis[i] == 0) { p[++ tot] = i; mu[i] = -1; }
		for(R int j = 1; j <= tot && i * p[j] < N; j ++) {
			vis[p[j] * i] = 1;
			if(i % p[j] == 0) {
				mu[i * p[j]] = 0; break;
			}
			mu[i * p[j]] = -mu[i];
		}
	}
	for(R int i = 1; i < N; i ++) 
		for(R int j = 1; j * i < N ; j ++) 
			sum[i * j] += 1LL * mu[i] * i * (j + 1) * j / 2;
	for(R int i = 1; i < N; i ++)	
		for(R int j = 1; j * i < N; j ++)
			f[i * j] += sum[j];
}

int T;

int main() {
	pre();
	T = read();
	while(T --) {
		int x = read();
		cout << x * f[x] << endl;	
	}	
	return 0;
}