算法

(积性函数、线性筛) $\mathcal{O}(N)$

$\operatorname{lcm}(i, n) = \dfrac{n \cdot i}{\gcd(i, n)}$

因为 $\gcd(i, n) \mid n$

我们可以枚举 $n$ 的因子 $d$

计算满足 $\gcd(i, n) = d \, (1 \leqslant i \leqslant n)$ 的 $\dfrac{i}{d}$ 之和

等价于 $\gcd(i, \frac{n}{d}) = 1 \, (1 \leqslant i \leqslant \frac{n}{d})$ 的 $i$ 之和

现在要求给定 $m = \frac{m}{d}$，求出小于 $m$ 的数中与 $m$ 互质的数的和。

我们知道这样的数一共有 $\varphi(m)$ 个

如果 $x$ 与 $m$ 互质，那么 $m-x$ 一定与 $m$ 互质。

因此，与 $m$ 互质的数可以两两配对，加起来等于 $m$

所以，总和就是 $m \times \frac{\varphi(m)}{2}$

因此答案等于

$$ n\sum_{d \mid n} \frac{\varphi(d)d}{2} = \frac{n}{2}\left(1 + \sum_{d \mid n} \varphi(d)d\right) $$

我们只要预处理 $\varphi$ 数组，然后枚举约数。

单次询问的时间复杂度就是 $O(\sqrt{n})$

还不够优秀。

我们关注函数：

$$ g(n) = \sum_{d \mid n} \varphi(d)d $$

因为 $\varphi(d)d$ 是积性的

所以 $g(n)$ 也是积性的

我们可以在线性筛的过程中筛出 $g(n)$

只需要考虑 $g(p^a)$ 如何计算。

$ \begin{aligned} g(p^a) &= 1 + (p-1)p + (p-1)pp^2 + \cdots + (p-1)p^2p^3 + (p-1)p^{a-1}p^a\\ &= 1 + p^2 - p + p^4 - p^3 + \cdots + p^{2a} - p^{2a-1}\\ &= p^2g(p^{a-1}) - p +1 \end{aligned} $

$g(p) = p^2 - p + 1$

这样就可以在线性筛的时候求出 $g$ 数组

这样单次询问的时间复杂度就是 $O(1)$ 了。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

// linear sieve
vector<bool> isp;
vector<int> ps, pf;
vector<ll> g, mincnt, remdiv; // mincnt: p^a  remdiv: n/p^a
void sieve(int mx) {
    isp.resize(mx+1);
    pf.resize(mx+1);
    g.resize(mx+1);
    mincnt.resize(mx+1);
    remdiv.resize(mx+1);
    rep(i, mx+1) pf[i] = i;
    g[1] = 1;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) {
            isp[i] = true, ps.push_back(i);
            g[i] = (ll)i*i-i+1;
            mincnt[i] = i;
            remdiv[i] = 1;
        }
        rep(j, ps.size()) {
            int x = ps[j]*i;
            if (x > mx) break;
            pf[x] = ps[j];
            if (i%ps[j] == 0) {
                remdiv[x] = remdiv[i];
                mincnt[x] = ps[j]*mincnt[i];
                g[x] = g[remdiv[i]]*(ps[j]*ps[j]*g[mincnt[i]] - ps[j] + 1);
                break;
            }
            g[x] = g[i]*g[ps[j]];
            mincnt[x] = ps[j];
            remdiv[x] = i;
        }
    }
}

int main() {
    sieve(1e6);

    cin.tie(nullptr) -> sync_with_stdio(false);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        ll ans = n*(1+g[n])/2;
        cout << ans << '\n';
    }

    return 0;
}