题解 | LCMS_牛客博客

LCMS

给你一个长度为 $n$ 的序列 $A_0,A_1,A_2,...,A_{n-1}$

求 $\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}lcm(A_i,A_j)\ mod\ 998244353$

其中 $2\le n \le 2e5,1 \le A_i \le 1e6$

思路

alt

对原式做等式变形

\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}lcm(A_i,A_j)*2 + \sum_{i=0}^{n-1} A_i= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}lcm(A_i,A_j)

又因为

Lcm(a,b)=\frac{a*b}{gcd(a,b)}

继续变形

\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}lcm(A_i,A_j) \\=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\frac{A_i*A_j}{gcd(A_i,A_j)} \\

记 $A_{i}$ 最大值为 $R$

问题就转化为了求

Ans =\sum_{d=1}^{R}\ \frac{1}{d}*\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} (A_i*A_j)\cdot[gcd(A_i,A_j)=d]

定义：

$f (d)$ 为 $g c d (A_{i}, A_{j}) = d$ 的总贡献

$F (d)$ 为 $g c d (A_{i}, A_{j})$ 为 $d$ 的倍数的总贡献

容易得

\begin{aligned} & f(d)=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(A_i*A_j)\cdot[gcd(A_i,A_j)=d] \\ &F(d)=\sum_{d|d'}f(d') \\ &=\sum_{d|d'} (\sum_{i=0}^{n-1}A_i\cdot[d|A_i]*\sum_{j=0}^{n-1}A_j\cdot[d|A_j]) \\ &=\sum_{d|d'} (\sum_{i=0}^{n-1}A_i\cdot[d|A_i])^2 \end{aligned}

莫比乌斯反演得

f(d)=\sum_{d|d'}\mu(\frac{d'}{d})\cdot F(d')

其中 $F (d^{'})$ 可以用枚举倍数的方法，预处理出来

然后再枚举 $d$ ,算出 $A n s$

Ans =\sum_{d=1}^{R}\ \frac{1}{d} *f(d)

不要忘了这个 $A n s$ 是 $\sum_{i=0}^{n-2}\sum_{j=i+1}^{n-1}lcm(A_i,A_j)*2 + \sum_{i=0}^{n-1} A_i= \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}lcm(A_i,A_j)$ 等式右边的答案，我们要求的是左边的那一项。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll mod = 998244353;
ll a[N], F[N], mp[N], f[N], inv[N];
int Primes[N], mbux[N], cnt;
bool vis[N];
void get_mbux(int x) {
    mbux[1] = 1;
    for (int i = 2; i <= x; i ++ ) {
        if(!vis[i]) {
            Primes[++ cnt] = i;
            mbux[i] = -1;
        }
        for (int j = 1; j <= cnt && i * Primes[j] <= x; j ++ ) {
            vis[i * Primes[j]] = 1;
            if(i % Primes[j] == 0 ) {
                mbux[i * Primes[j]] = 0;
                break;
            }
            mbux[i * Primes[j]] = - mbux[i];
        }
    }
} 
int main() {
    // 线性筛求莫比乌斯
    get_mbux(N-1);
    // 预处理逆元
    inv[1] = 1;
    for (int i = 2; i <= N-1; i ++) inv[i] = inv[mod%i] * (mod-mod/i) % mod;
    int n;
    scanf("%d", &n);
    ll Maxx = 0, sum = 0, res = 0;
    for (int i = 1; i <= n; i ++ ) {
    	scanf("%lld", &a[i]);
    	Maxx = max(Maxx, a[i]);
    	mp[a[i]] ++;
    	sum += a[i];
        sum %= mod;
	}
	// 预处理 F 
	for (int i = 1; i <= Maxx; i ++ ) {
		for (int j = i; j <= Maxx; j += i) {
			F[i] += mp[j] * j;
			F[i] %= mod;
		}
		F[i] = (F[i] * F[i]) % mod;
	}
	// 算 f
	for (int i = 1; i <= Maxx; i ++ ) {
		for (int j = i; j <= Maxx; j += i) {
			f[i] = (f[i] + mbux[j/i] * F[j] % mod + mod) % mod;
		}
		res = (res + inv[i] * f[i] + mod ) % mod;
	} 
	res = ((res - sum + mod) * inv[2]) % mod;
	printf("%lld\n", res);
}