Link

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;
}