Description
给定 \(n\)，求 \(\sum\limits_{i = 1}^n \operatorname{lcm}(i, n)\)，多组数据，有 \(3e5\) 组数据，\(n\le 1e6\)。
Solution
\(\sum\limits_{i = 1} ^n \operatorname{lcm}(i, n) = \sum\limits_{i = 1} ^n \dfrac{in}{\gcd(i, n)} = n\sum\limits_{i = 1}^n \dfrac{i}{\gcd(i, n)}\)
考虑贡献，枚举 \(d = \gcd(i, n)\)，则有 \(n\sum\limits_{i = 1}^n \dfrac{i}{d} = n\sum\limits_{i = 1}^n\sum\limits_{d|n, d|i}\dfrac{i}{d}\times [\gcd(n/d, i/d)] = n\sum\limits_{d|n}\sum\limits_{k = 1}^{\lfloor \frac{n}{d}\rfloor} k[\gcd(k, \dfrac{n}{d}) = 1]\)
显然 \(\dfrac{n}{d}\) 与 \(d\) 是等价的。因此有 \(n\sum\limits_{d|n}\sum\limits_{k = 1}^{d} k[\gcd(k, d) = 1]\)。对于单独的 \(d\) 就是计算比它小的与其互质的数字的数量。
这又涉及一个欧拉函数的性质，与 \(n\) 互质且小于等于 \(n\) 的数字的和是 \(\dfrac{\varphi(n)n}{2}\)。这是因为 \(\gcd(n - x, n)\)，那么每个与 \(n\) 互质的数字是成双成对出现的，而且和为 \(n\)，一共有 \(\dfrac{\varphi(n)}{2}\) 个这样的对，和为 \(\dfrac{\varphi(n)n}{2}\)。
那么答案就成了 \(n\sum\limits_{d|n}\dfrac{\varphi(d)d}{2}\)。
这个东西是我六年级暑假学的（捂脸），然后现在全忘了（捂脸），是时候重新看一遍了（捂脸）。
//SIXIANG
#include <cstdio>
#define MAXN 1000000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int phi[MAXN + 10];
void getphi() {
for(int p = 1; p <= MAXN; p++) phi[p] = p;
for(int p = 2; p <= MAXN; p++)
if(phi[p] == p)
for(int i = p; i <= MAXN; i += p)
phi[i] = phi[i] / p * (p - 1);
}
long long solve(int n) {
long long ans = 0;
for(int p = 1; p * p <= n; p++) {
if(p == 1) {
ans++;
ans += 1ll * phi[n] * n / 2;
continue;
}
if(n % p == 0) {
if(p * p == n) ans += 1ll * phi[p] * p / 2;
else ans = ans + 1ll * phi[p] * p / 2 + 1ll * phi[n / p] * (n / p) / 2;
}
}
return ans * 1ll * n;
}
signed main() {
getphi();
int T, n;
scanf("%d", &T);//ios+cin 都过不去，scanf+printf 跑得飞起，懒狗落泪(╥╯^╰╥)
for(int p = 1; p <= T; p++) {
scanf("%d", &n);
printf("%lld\n", solve(n));
}
}