CF1285F Classical? 题解
jiangly
·
·
题解
题意
给出 n 个数 a_1,a_2,\ldots,a_n，求
\max_{1\le i<j\le n}\mathrm{lcm}(a_i,a_j)
限制
#### 题解
令 $A=\max\{a_i\}$。
考虑加上 $\gcd(a_i,a_j)=1$ 的限制。从大到小扫集合里的数，可以发现如果扫到 $x$ 时存在 $y>x$ 且 $\gcd(x,y)=1$，则所有满足 $x<z<y$ 的数 $z$ 不会对答案有贡献了。因此用栈储存扫过的元素，扫到一个数 $x$ 时，只要栈中有与 $x$ 互素的数就弹栈，并与 $x$ 更新答案。如何快速判断是否有与 $x$ 互素的数？考虑容斥。记 $\mathrm{cnt}_i$ 为 $i$ 的倍数的个数，则与 $x$ 互素的数的个数为
$$
\sum_{d|x}\mu(d)\mathrm{cnt}_d
$$
这个过程的复杂度为 $O(\sum_{i=1}^Ad(i))=O(A\log A)$。
接下来可以枚举 $\gcd(a_i,a_j)=g$ 并对所有 $g$ 的倍数执行上述过程，时间复杂度 $O(A(\log A)^2)$。
更巧妙的做法是把每个 $a_i$ 的所有因数加入集合。假设原始的答案由 $x$ 和 $y$ 两个数得到，则一定存在两个数 $a\mid x,b\mid y$ 满足 $\mathrm{lcm}(a,b)=\mathrm{lcm}(x,y)$ 且 $\gcd(a,b)=1$，因此只需要执行一次上述过程。时间复杂度：$O(A\log A)$。
#### 代码
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
int n;
std::vector<bool> a;
std::vector<int> stk, cnt, mu;
std::vector<std::vector<int>> divisors;
long long ans;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
if (int(a.size()) <= x)
a.resize(x + 1);
a[x] = true;
ans = std::max(ans, 1LL * x);
}
int m = a.size() - 1;
mu.resize(m + 1);
mu[1] = 1;
for (int i = 1; i <= m; ++i)
for (int j = 2 * i; j <= m; j += i)
mu[j] -= mu[i];
divisors.resize(m + 1);
for (int i = 1; i <= m; ++i) {
for (int j = i; j <= m; j += i) {
if (mu[i] != 0)
divisors[j].push_back(i);
a[i] = a[i] || a[j];
}
}
cnt.resize(m + 1);
for (int i = m; i >= 1; --i) {
if (!a[i])
continue;
int num = 0;
for (int j : divisors[i])
num += mu[j] * cnt[j];
while (num > 0) {
int lst = num;
for (int j : divisors[stk.back()]) {
--cnt[j];
if (i % j == 0)
num -= mu[j];
}
if (lst != num)
ans = std::max(ans, 1LL * i * stk.back());
stk.pop_back();
}
for (int j : divisors[i])
++cnt[j];
stk.push_back(i);
}
std::cout << ans << "\n";
return 0;
}
```