AGC038C LCMs

记录每个数出现的个数 $c _ i$ 。要求 $\sum _ {i = 1} ^ n \sum _ {j = i + 1} ^ n \text{lcm} (A _ i, A _ j)$ ，可以求 $\sum _ {i = 1} ^ n \sum _ {j = 1} ^ n \text{lcm} (A _ i, A _ j)$ ，然后将每个数减去，再除以 $2$ 。
$$
\begin {aligned}
& \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n \text{lcm} (i, j) c_ i c_ j \\
= & \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n \frac {ij} {(i, j)}c _ ic _ j \\
= & \sum _ {i = 1} ^ n \sum _ {j = 1} ^ n \sum _ {d = 1} ^ n \frac {ij} d c _ ic _ j [(i, j) = d]\\
= & \sum _ {d = 1} ^ n \sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor } \frac {idjd} d c _ {id}c _ {jd} [(id, jd) = d]\\
= & \sum _ {d = 1} ^ n d\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor } ij c _ {id}c _ {jd} [(i, j) = 1]\\
= & \sum _ {d = 1} ^ n d\sum _ {i = 1} ^ {\lfloor \frac n d \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n d \rfloor } ij c _ {id}c _ {jd} \sum _ {e | (i, j)}\mu (e)\\
= & \sum _ {d = 1} ^ n d \sum _ {e = 1} ^ n \mu(e) e ^ 2 \sum _ {i = 1} ^ {\lfloor \frac n {de} \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n {de} \rfloor } ij c _ {ide}c _ {jde}\\
\end {aligned}
$$
令 $T = de$ 。
$$
\begin {aligned}
& \sum _ {d = 1} ^ n d \sum _ {e = 1} ^ n \mu(e) e ^ 2 \sum _ {i = 1} ^ {\lfloor \frac n {de} \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n {de} \rfloor } ij c _ {ide}c _ {jde}\\
= & \sum _ {T = 1} ^ n T \sum _ {e |T} \mu(e) e \sum _ {i = 1} ^ {\lfloor \frac n T \rfloor } \sum _ {j = 1} ^ {\lfloor \frac n T \rfloor } ij c _ {iT}c _ {jT}\\
= & \sum _ {T = 1} ^ n T \sum _ {e |T} \mu(e) e (\sum _ {i = 1} ^ {\lfloor \frac n T \rfloor }ic _ {iT}) (\sum _ {j = 1} ^ {\lfloor \frac n T \rfloor }jc _ {jT})\\
= & \sum _ {T = 1} ^ n T \sum _ {e |T}\mu(e) e (\sum _ {i = 1} ^ {\lfloor \frac n T \rfloor }ic _ {iT}) ^ 2\\
\end {aligned}
$$
直接暴力计算即可。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int n = 1e6, N = n + 10, mod = 998244353, inv2 = 499122177;
int m, c[N], f[N];
bool vis[N];
int cnt, p[N], mu[N];
void init ()
{
    vis[1] = true;
    mu[1] = 1;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) mu[p[++cnt] = i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
                { mu[i * p[j]] = 0; break; }
            mu[i * p[j]] = mu[i] * mu[p[j]];
        }
    }
}
int main ()
{
    init();
    read(m);
    for (int a; m; --m) read(a), ++c[a];
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            (f[j] += mu[i] * i) %= mod;
    for (int i = 1; i <= n; ++i)
    {
        int t = 0;
        for (int j = 1; j <= n / i; ++j)
            (t += (LL)c[i * j] * j % mod) %= mod;
        f[i] = (LL)f[i] * t % mod * t % mod * i % mod;
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) (res += f[i]) %= mod;
    for (int i = 1; i <= n; ++i)
        (res -= (LL)i * c[i] % mod) %= mod;
    write(((LL)res * inv2 % mod + mod) % mod);
    return 0;
}