提出 #23344585

---

ソースコード 拡げる

// agc038_c
// LCMs

#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1000010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b;
ll f[maxn], s1[maxn], s2[maxn], tt[maxn], dp[maxn];
ll nv[maxn];

ll fxp(ll b, ll e) {
    ll r;
    if (e == 0) return 1;
    if (e % 2) {
        r = fxp(b, e - 1); return (b * r) % mod;
    } else {
        r = fxp(b, e / 2); return (r * r) % mod;
    }
}

ll inv(ll x) {
    return fxp(x, mod - 2);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    for (i = 1; i < maxn; i++) nv[i] = inv(i);

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i]; f[a[i]]++;
    }

    for (i = 1; i < maxn; i++) {
        for (j = i; j < maxn; j += i) {
            s1[i] += (f[j] * j); s1[i] %= mod;
            s2[i] += (f[j] * j * j); s2[i] %= mod;
        }
    }

    for (i = 1; i < maxn; i++) {
        tt[i] = (s1[i] * s1[i] - s2[i] + mod) % mod;
        if (s1[i] != 0 || s2[i] != 0) {
            // cout << "tt " << i _ s1[i] _ s2[i] _ tt[i] << nl;
        }
    }

    for (i = maxn - 1; i >= 1; i--) {
        dp[i] = tt[i];
        for (j = 2 * i; j < maxn; j += i) {
            dp[i] = (dp[i] - dp[j] + mod) % mod;
        }
        res += (dp[i] * nv[i]); res %= mod;
        if (dp[i] != 0) {
            // cout << "dp " << i _ dp[i] << nl;
        }
    }

    res *= nv[2]; res %= mod;

    cout << res << nl;

    return 0;
}

提出情報

ジャッジ結果