洛谷P3911 最小公倍数之和 题解 莫比乌斯反演

题目链接：https://www.luogu.com.cn/problem/P3911

题目大意：

给你一个长度为 \(N\) 的数列 \(A_1, A_2, \ldots, A_N\)，求

\[\sum_{i=1}^N \sum_{j=1}^N \operatorname{lcm}(A_i, A_j) \]

---

解题思路：

用 \(M\) 表示 \(A\) 数组中所有元素的最大值，即

\[M = \max_{1 \le i \le N} a_i \]

用 \(C_x\) 表示数字 \(x\) 在 \(A\) 数组中的出现次数，则答案为

\[\sum_{i=1}^M \sum_{j=1}^M \operatorname{lcm}(i, j) \cdot C_i \cdot C_j \]

由于 \(\operatorname{lcm}(i, j) = \frac{i \cdot j}{\gcd(i, j)}\)

所以答案可以表示为

\[\sum_{i=1}^M \sum_{j=1}^M \frac{i \cdot j}{ \gcd(i, j) } \cdot C_i \cdot C_j \]

如果我们令 \(d = \gcd(i, j)\)，然后枚举 \(d\)，可以得到答案为

\[\sum_{d=1}^M \sum_{i=1}^M \sum_{j=1}^M [ \gcd(i, j) = d ] \cdot \frac{i \cdot j}{d} \cdot C_i \cdot C_j \]

这里，中括号是艾弗森运算符，成立为 \(1\)，不成立为 \(0\)。

上式等价于

\[\sum_{d=1}^{M} d \sum_{i=1}^{M/d} \sum_{j=1}^{M/d} [\gcd(i,j) = 1] \cdot (i \cdot C_{id}) \cdot (j \cdot C_{jd}) \]

接下来引入莫比乌斯反演

莫比乌斯反演最常用的性质是：

\[[\gcd(i,j)=1] = \sum_{k \mid \gcd(i,j)} \mu(k) \]

代入上方刚才推导的式子的答案为

\[\sum_{d=1}^{M} d \sum_{k=1}^{M/d} \mu(k) \sum_{k \mid i, i \le M/d} \sum_{k \mid j, j \le M/d} (i \cdot C_{id}) \cdot (j \cdot C_{jd}) \]

这个时候，最右边的两个 sigma 是可以化简的

用 \(ik\) 表示 \(i\)，\(jk\) 表示 \(j\)，即可以将

\[\sum_{k \mid i, i \le M/d} \sum_{k \mid j, j \le M/d} (i \cdot C_{id}) \cdot (j \cdot C_{jd}) \]

化简为

\[\sum_{i=1}^{M/(dk)} \sum_{j=1}^{M/(dk)} (ik \cdot C_{idk}) \cdot (jk \cdot C_{jdk}) \]

\[= k^2 \left( \sum_{i=1}^{M/(dk)} i \cdot C_{idk} \right)^2 \]

代入到答案的公式得，答案为

\[\sum_{d=1}^{M} d \sum_{k=1}^{M/d} \mu(k) \cdot k^2 \left( \sum_{i=1}^{M/(dk)} i \cdot C_{idk} \right)^2 \]

此时，计算上述式子需要三重循环，会超时。

令 \(T = dk\)，然后将原来的 “枚举 \(d\) 和 \(k\)” 转变为 “枚举 \(T\) 和 \(d\)”，则答案的式子转换为

\[\sum_{T=1}^M \sum_{d \mid T} d \cdot \mu(\frac{T}{d}) \cdot (\frac{T}{d})^2 \left( \sum_{i=1}^{M/T} i \cdot C_{iT} \right)^2 \]

再转换一下就是

\[\sum_{T=1}^M \sum_{d \mid T} T \cdot \mu(\frac{T}{d}) \cdot (\frac{T}{d}) \cdot \left( \sum_{i=1}^{M/T} i \cdot C_{iT} \right)^2 \]

把 \(T\) 提到最前面来，最后那个 sigma 用 \(d\) 替换 \(\frac{T}{d}\)，有

\[\sum_{T=1}^M T \left( \sum_{d \mid T} \mu(d) \cdot d \right) \cdot \left( \sum_{i=1}^{M/T} i \cdot C_{iT} \right)^2 \]

第一个括号中的 sigma 可以 \(O(M \log M)\) 预处理得到，然后查询就是 \(O(1)\) 了。

第二个括号中的 sigma 可以直接暴力，暴力时间复杂度 \(O(M/T)\)。

而 \(O(T \cdot (M / T)) = O(M^2)\)。

所以总时间复杂度为 \(O(M^2)\)。

示例程序：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e4, maxn = N + 5;

int n, c[maxn], m, mu[maxn];
long long sum[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 0, a; i < n; i++) {
        scanf("%d", &a);
        c[a]++;
        m = max(m, a);
    }
    mu[1] = 1;
    for (int i = 2; i <= m; i++) {
        mu[i] = -1;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                if (i / j % j)
                    mu[i] = mu[i / j] * (-1);
                else
                    mu[i] = 0;
                break;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int d = 1; d * d <= i; d++) {
            if (i % d == 0) {
                sum[i] += mu[d] * d;
                if (d * d < i)
                    sum[i] += mu[i/d] * (i/d);
            }
        }
    }
    ll ans = 0;
    for (int t = 1; t <= m; t++) {
        ll tmp = 0;
        for (int i = 1; i <= m/t; i++)
            tmp += i * c[i * t];
        ans += 1ll * t * sum[t] * tmp * tmp;
    }
    printf("%lld\n", ans);
    return 0;
}