Sol
主要考察的是 $gcd$ 和 $lcm$ 关系的一个性质: $lcm(a, b) = \frac{a \times b}{gcd(a,b)}$
那么我们用这个式子来替换现在的式子
$$\sum_{i=1}^{n} \frac{i \times n}{gcd(i,n)}$$
把乘的 $n$ 这个常数项直接提到外面来,稍微改改
$$n \times \sum_{i=1}^{n} \frac{i}{gcd(i,n)}$$
常见套路:有整除,gcd,约数的时候,把枚举的东西改成枚举约数,再改成枚举倍数
那么我们先枚举约数试试
$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(i,n) = d]$$
再把中括号(布尔表达式)内的东西同时除一个 $d$
$$n \times \sum_{d|n} \sum_{i=1}^{n} \frac{i}{d} [gcd(\frac{i}{d}, \frac{n}{d}) = 1]$$
再写成枚举倍数的
$$n \times \sum_{d|n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i [gcd(i,\frac{n}{d}) = 1]$$
注意到因为 $d|n$,所以 $\frac{n}{d}$ 与 $d$ 等价,全部改成枚举到 $d$
$$n \times \sum_{d|n} \sum_{i=1}^{d} i [gcd(i,d) = 1]$$
现在应该很显然, $[gcd(i,d)=1]$ 就是 $\varphi(d)$
实际上因为 $n$ 的约数是成对出现的,那么一共会有 $\frac{d}{2}$ 对约数,直接把后面的东西利用这个性质算出来.
所以现在就是
$$n \times \sum_{d|n} \frac{\varphi(d)}{2} \times d $$
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 1e6 + 5;
int T, n, tot;
int prime[SIZE], phi[SIZE], isPrime[SIZE], ans[SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
inline void euler()
{
int siz = 1e6 + 1;
phi[1] = isPrime[1] = 1;
for (register int i = 2; i <= siz; ++ i) {
if (!isPrime[i]) {
prime[++ tot] = i, phi[i] = i - 1;
}
for (register int j = 1; j <= tot && i * prime[j] <= siz; ++ j) {
isPrime[i * prime[j]] = 1;
if (i % prime[j]) phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
signed main()
{
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
T = read();
euler(); int siz = 1e6 + 1;
for (int i = 1; i <= siz; ++ i) {
for(int j = 1; i * j <= siz; ++ j)
ans[i * j] += (i == 1 ? 1 : 1ll * phi[i] * i / 2);
}
while (T --) {
n = read();
printf("%lld\n", ans[n] * n * 1ll);
// puts("");
}
return 0;
}