LOJ

分析

可以发现答案即为
$$
\sum_{i = 1}^n {\sigma_0(i) \choose 2}
$$
把组合数拆掉变成
$$
\sum_{i = 1}^n \frac{\sigma_0(i) (\sigma_0(i) - 1)}{2}
$$
于是我们需要计算 $\sigma_0$ 的前缀和与 $\sigma_0\!^2$ 的前缀和。

先考虑 $\sum \sigma_0(i)$，即 $[1,n]$ 中每个数的约数个数和，考虑每个数的倍数个数可以得到其等于
$$
\sum_{i = 1}^n \left\lfloor\frac{n}{i}\right\rfloor
$$
数论分块计算即可。

再考虑 $\sum \sigma_0\!^2(i)$。我们知道 $\sigma_0\!^2$ 是积性函数，且有 $\sigma_0\!^2(p) = 4$、$\sigma_0\!^2(p ^ k) = (k + 1) ^ 2$，因此可以使用 Min_25 筛计算。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
    ll X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 200000 + 10;
const int mod = 998244353, inv2 = 499122177, inv6 = 166374059;

ll n; int S;
ll w[N];
int id1[N], id2[N], top = 0, g[N];

int S3(int n) {
    return 1ll * n * (n + 1) % mod * (n + n + 1) % mod * inv6 % mod;
}

int p[N], v[N], pcnt = 0;
void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!v[i]) p[++pcnt] = i;
        for (int j = 1; j <= pcnt && i * p[j] <= n; ++j) {
            v[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

int S_(ll x, int j) {
    if (x <= 1 || p[j] > x) return 0;
    int k = x <= S ? id1[x] : id2[n / x];
    int res = 4ll * (g[k] - (j - 1) + mod) % mod;
    for (int i = j; i <= pcnt && 1ll * p[i] * p[i] <= x; ++i) {
        ll p1 = p[i], p2 = 1ll * p[i] * p[i];
        for (int e = 1; p2 <= x; ++e, p1 = p2, p2 *= p[i])
            res = (res + 1ll * S_(x / p1, i + 1) * (e + 1) * (e + 1) % mod + (e + 2) * (e + 2)) % mod;
    }
    return res;
}

int main() {
    n = read(), S = sqrt(n); sieve(S);
    int ans = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        ans = (ans + (n / l) % mod * (r - l + 1)) % mod;
    }
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l); w[++top] = n / l;
        if (n / l <= S) id1[n / l] = top;
        else id2[n / (n / l)] = top;
        g[top] = (n / l) % mod - 1;
    }
    for (int i = 1; i <= pcnt; ++i)
        for (int j = 1; j <= top && 1ll * p[i] * p[i] <= w[j]; ++j) {
            ll x = w[j] / p[i]; int k = x <= S ? id1[x] : id2[n / x];
            g[j] = (g[j] - g[k] + mod + (i - 1)) % mod;
        }
    printf("%d\n", 1ll * (S_(n, 1) + 1 - ans + mod) * inv2 % mod);
    return 0;
}