题目链接:P3911 最小公倍数之和
题目大意
简洁易懂,我就不说了
solution
我们来观察这个式子, (lcm)怎么操作啊? 那我们就转化成(gcd)
(sumlimits_{i = 1}^nsumlimits_{j = 1}^n lcm(A_i, A_j) iff sumlimits_{i = 1}^nsumlimits_{j = 1}^n dfrac{A_iA_j}{gcd(A_i, A_j)})
那还是很难处理啊, 那我们怎么办呢, 我们是不是可以转化成值域来做啊,记录一下每个数的个数.
我们发现这样是可行的, 毕竟 (A_i in [1, 50000])
我们设 (N) 为值域的最大值, (C_i) 是每个元素的个数, 那我们要求的就变成了:
(sumlimits_{i = 1}^Nsumlimits_{j = 1}^N dfrac{i imes j imes C_i imes C_j}{gcd(A_i, A_j)})
这不就是莫比乌斯反演的板子题么, 那我们来推一下反演过程:
枚举公约数:
(sumlimits_{d = 1}^Nsumlimits_{i = 1}^Nsumlimits_{j = 1}^N dfrac{ij}{d}[gcd(A_i, A_j) == d] imes C_i imes C_j)
将后两重循环除以 (d) , (i) 和 (j) 变成 (id) 和 (jd) :
(sumlimits_{d = 1}^Nsumlimits_{i = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{d} ight floor} ijd[gcd(A_i, A_j) == 1] imes C_{id} imes C_{jd})
我们伟大的莫比乌斯函数来了:
(sumlimits_{d = 1}^Nsumlimits_{i = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{k|gcd(i, j)} mu(k)ijd imes C_{id} imes C_{jd})
我们发现 (gcd(i,j) == 1), 共有 (leftlfloorfrac{N}{d} ight floor) 个, 然后改变一下 (k) 的枚举方式:
(sumlimits_{d = 1}^Nsumlimits_{i = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{k}^{leftlfloorfrac{N}{d} ight floor} mu(k)ijd imes C_{id} imes C_{jd})
交换一下枚举顺序:
(sumlimits_{d = 1}^Nsumlimits_{k}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{i = 1}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{d} ight floor} mu(k)ijd imes C_{id} imes C_{jd})
然后将最后两重循环除以 (k), (id, jd) 就变成了 (idk, jdk) :
(sumlimits_{d = 1}^Nsumlimits_{k}^{leftlfloorfrac{N}{d} ight floor}sumlimits_{i = 1}^{leftlfloorfrac{N}{dk} ight floor}sumlimits_{j = }^{leftlfloorfrac{N}{dk} ight floor} mu(k)ijdk^2 imes C_{idk} imes C_{jdk})
我们令 (T = dk) :
(sumlimits_{T = 1}^Nsumlimits_{k | T}sumlimits_{i = 1}^{leftlfloorfrac{N}{T} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{T} ight floor} mu(k)k T ij imes C_{iT} imes C_{jT})
然后交换一下枚举顺序:
(sumlimits_{T = 1}^N T sumlimits_{i = 1}^{leftlfloorfrac{N}{T} ight floor}sumlimits_{j = 1}^{leftlfloorfrac{N}{T} ight floor} ij imes C_{iT} imes C_{jT}sumlimits_{k | T}mu(k)k)
把 (ij) 的两维合并:
(sumlimits_{T = 1}^N T sumlimits_{i = 1}^{leftlfloorfrac{N}{T} ight floor} (i imes C_{iT})^2sumlimits_{k | T}mu(k)k)
最后我们预处理出 (mu(k)k) 就做完了.
Code:
/**
* Author: Alieme
* Data: 2020.9.8
* Problem: P3911
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define rr register
#define inf 1e9
#define MAXN 100010
using namespace std;
inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int tot, n, ans;
int c[MAXN], mu[MAXN], prime[MAXN], sum[MAXN];
bool vis[MAXN];
inline void init() { // 预处理mu和公式
mu[1] = 1;
for (rr int i = 2; i <= 50000; i++) { // 线性筛预处理mu
if (!vis[i]) prime[++tot] = i, mu[i] = -1;
for (rr int j = 1; j <= tot; j++) {
if (i * prime[j] > 50000) break;
vis[i * prime[j]] = 1;
mu[i * prime[j]] = -mu[i];
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
}
}
for (rr int i = 1; i <= 50000; i++) // 预处理 mu(k)*k
for (rr int j = i; j <= 50000; j += i)
sum[j] += mu[i] * i;
}
signed main() {
init();
n = read();
for (rr int i = 1; i <= n; i++) c[read()]++;
for (rr int i = 1; i <= 50000; i++) { // 暴力求解
int s = 0;
for (rr int j = 1; j <= 50000 / i; j++) s += c[i * j] * j;
ans += i * s * s * sum[i];
}
print(ans);
}