DDOSvoid's Blog

AtCoder AGC038C LCMs

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://atcoder.jp/contests/agc038/tasks/agc038_c

简要题意：求 $\sum_{i=1}^n\sum_{j=1}^n[a_i,a_j]$​

$n\le 2\times 10^5,a_i\le 10^6$

Solution

令 $N=max\lbrace a_i\rbrace$

这个东西可以 $O(n\log n)$ 做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#define maxn 200010
#define maxm 1000010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
} 

int n, a[maxn];

int pri[maxm], c1, mu[maxm]; bool isp[maxm]; ll f[maxm];
void init_isp(int n) {
    mu[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++c1] = i, mu[i] = -1; 
        for (int j = 1; j <= c1 && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) { mu[i * pri[j]] = 0; continue; }
            mu[i * pri[j]] = -mu[i];
        } 
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) f[j] = (f[j] + i * mu[i]) % p;
    for (int i = 1; i <= n; ++i) f[i] = f[i] * pow_mod(i, p - 2) % p; 
}

int cnt[maxm];

ll g[maxm];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; int N; init_isp(N = 1000000); 
    for (int i = 1; i <= n; ++i) cin >> a[i], ++cnt[a[i]];
    for (int i = 1; i <= N; ++i) { 
        for (int j = i; j <= N; j += i) g[i] = (g[i] + 1ll * j * cnt[j]) % p;
        g[i] = g[i] * g[i] % p; 
    } ll ans = 0;
    for (int i = 1; i <= N; ++i) ans = (ans + f[i] * g[i]) % p;
    for (int i = 1; i <= n; ++i) ans = (ans - a[i]) % p;
    ans = ans * pow_mod(2, p - 2) % p; 
    cout << (ans + p) % p << "\n"; 
    return 0;
}