NC229749 - LCMs

题意

给你一个长度为的序列.

求

前置知识

莫比乌斯反演

思路

观察发现：

显然左式比较好求，我们可以通过求解左式来或得答案，

因为，

那么我们可以将上面式子变成：

接着这个式子可以转换成：

其中

我们设

接着设，可以发现就表示为倍数的任意两个的乘积之和，

就可以通过预处理倍数的所有来计算

然后根据莫比乌斯反演：

那么就可以最终答案为：

代码

/**
 *    author: andif
 *    created: 30.09.2023 17:30:37
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int mod = 998244353;

int kpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) {
            ret = 1ll * ret * a % mod;
        }
        a = (1ll * a * a) % mod;
        b >>= 1;
    }
    return ret;
}

vi get_mo(int n) {
    auto calc_f = [&] (int p, int a) {
        return a > 1 ? 0 : -1;
    };
    vi mo(n + 1);
    vi p, is_p(n + 1, 1), cnt(n + 1);
    mo[1] = 1; is_p[1] = 0;
    for (int i = 2; i <= n; ++i) {
        if (is_p[i]) {
            p.eb(i);
            mo[i] = -1;
            cnt[i] = 1;
        }
        for (int j = 0; j < sz(p) && i * p[j] <= n; ++j) {
            int k = i * p[j];
            is_p[k] = 0;
            if (i % p[j] == 0) {
                cnt[k] = cnt[i] + 1;
                mo[k] = mo[i] / calc_f(p[j], cnt[i]) * calc_f(p[j], cnt[k]);
                break;
            }
            mo[k] = mo[i] * mo[p[j]];
            cnt[k] = 1;
        }
    }
    return mo;
}

int main() {
    qc;
    int n; cin >> n;
    vi a(n);
    rep(i, 0, n) cin >> a[i];
    int L = *max_element(all(a));
    vi vis(L + 1, 0);
    rep(i, 0, n) vis[a[i]]++;
    // de(L);
    vi mo = get_mo(L);
    vi b(L + 1);
    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j * i <= L; ++j) {
            int k = j * i;
            if (vis[k]) b[i] = (1ll * b[i] + 1ll * vis[k] * k) % mod;
        }
        // dd(i), de(b[i]);
    }
    vi g(L + 1);
    for (int i = 1; i <= L; ++i) {
        g[i] = 1ll * b[i] * b[i] % mod;
        // dd(i), de(g[i]);
    }
    vi f(L + 1);
    for (int i = 1; i <= L; ++i) {
        for (int j = 1; j * i <= L; ++j) {
            int k = i * j;
            f[i] = (f[i] + 1ll * g[k] * mo[j] % mod) % mod;
            if (f[i] < 0) f[i] += mod;
        }
        // dd(i), de(f[i]);
    }
    int sum = 0;
    for (int i = 1; i <= L; ++i) {
        // dd(i), dd(mod), dd(kpow(i, mod - 2)), de(f[i]);
        sum = (sum + 1ll * f[i] * kpow(i, mod - 2) % mod) % mod;
    }
    // de(sum);
    int ans = sum;
    for (int i = 0; i < n; ++i) {
        ans = (ans - a[i]) % mod;
        if (ans < 0) ans += mod;
    }
    ans = 1ll * ans * kpow(2, mod - 2) % mod;
    cout << ans << '\n';
    return 0;
}