P3911 最小公倍数之和

Description

• 给定整数 $n$ 和 $n$ 个整数 $a_1,a_2,\dots ,a_n$，求
  $$\sum _{i=1}^n\sum _{j=1}^n\mathrm{lcm}(a_i,a_j)$$

• 对于 $100\%$ 的数据，$1\le n,a_i\le 5\times 10^4$。

Solution

直接反演不行，考虑计算贡献。

设 max⁡{a1,a2,…,an}=m\max\{a_1, a_2, \dots, a_n\} = mmax{a1​,a2​,…,an​}=m。

观察到值域（即 $m$）$\le 5\times 10^4$，开一个数组 $c_i$ 记录数 $i$ 的出现次数。
$$\begin{array}{rl}\sum _{i=1}^n\sum _{j=1}^n\mathrm{lcm}(a_i,a_j)& =\sum _{i=1}^m\sum _{j=1}^m\mathrm{lcm}(i,j)c_i{c}_j\\ & =\sum _{i=1}^m\sum _{j=1}^m\frac{ij}{\gcd (i,j)}{c}_i{c}_j\\ & =\sum _{i=1}^m\sum _{j=1}^m\sum _{d=1}^m\frac{ij}{d}[\gcd (i,j)=d]c_i{c}_j\\ & =\sum _{d=1}^m\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }\frac{(id)(jd)}{d}[\gcd (i,j)=1]c_{id}{c}_{jd}\\ & =\sum _{d=1}^m\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }ijd{c}_{id}{c}_{jd}\sum _{k\mid \gcd (i,j)}\mu (k)\\ & =\sum _{d=1}^{m}d\sum _{k=1}^{\lfloor \frac{m}{d}\rfloor }\mu (k)\sum _{i=1}^{\lfloor \frac{m}{d}\rfloor }[k\mid i]i{c}_{id}\sum _{j=1}^{\lfloor \frac{m}{d}\rfloor }[k\mid j]j{c}_{jd}\\ & =\sum _{d=1}^{m}d\sum _{k=1}^{\lfloor \frac{m}{d}\rfloor }\mu (k){\left(\sum _{i=1}^{\lfloor \frac{m}{dk}\rfloor }ik{c}_{idk}\right)}^2\\ & =\sum _{d=1}^{m}d\sum _{k=1}^{\lfloor \frac{m}{d}\rfloor }\mu (k)k^2{\left(\sum _{i=1}^{\lfloor \frac{m}{T}\rfloor }i{c}_{iT}\right)}^2\\ & =\sum _{T=1}^m{\left(\sum _{i=1}^{\lfloor \frac{m}{T}\rfloor }i{c}_{iT}\right)}^2\sum _{k\mid T}\mu (k)k^2\left(\frac{T}{k}\right)\\ & =\sum _{T=1}^{m}T{\left(\sum _{i=1}^{\lfloor \frac{m}{T}\rfloor }i{c}_{iT}\right)}^2\sum _{k\mid T}\mu (k)k\\ & =\sum _{T=1}^{m}T{\left(\sum _{i=1}^{\lfloor \frac{m}{T}\rfloor }i{c}_{iT}\right)}^2\sum _{k\mid T}\mu (k)k\end{array}$$
首先 $\mu$ 的线性筛是 $\mathrm{O}(m)$ 的。

对于 ${\sum }_{k\mid T}\mu (k)k$，用经典套路枚举倍数 $\Theta \left(\frac{m}{1}+\frac{m}{2}+\frac{m}{3}+\cdots \right)=\Theta (m\ln m)$ 预处理。

${\sum }_{T=1}^{m}T{\left({\sum }_{i=1}^{\lfloor \frac{m}{T}\rfloor }i{c}_{iT}\right)}^2$ 直接暴力也是 $\Theta (m\ln m)$ 的。

总时间复杂度为 $\Theta (m\ln m)$。还带大常数

Code

// 18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#define Debug(x) cout << #x << "=" << x << endl
#define int long long
using namespace std;const int MAXN = 5e4 + 5;
const int N = 5e4;int p[MAXN], mu[MAXN], res[MAXN];
bool vis[MAXN];void pre()
{mu[1] = 1;for (int i = 2; i <= N; i++){if (!vis[i]){p[++p[0]] = i;mu[i] = -1;}for (int j = 1; j <= p[0] && 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]];}}for (int i = 1; i <= N; i++){for (int j = 1; i * j <= N; j++){res[i * j] += mu[i] * i;}}
}int a[MAXN], c[MAXN];signed main()
{pre();int n, m = 0;scanf("%lld", &n);for (int i = 1; i <= n; i++){scanf("%lld", a + i);m = max(m, a[i]);c[a[i]]++;}int ans = 0;for (int i = 1; i <= m; i++){int tmp = 0;for (int j = 1; j <= m / i; j++){tmp += j * c[j * i];}ans += i * tmp * tmp * res[i];}printf("%lld\n", ans);return 0;
}