CF1285F Classical?

题意

给定 $n$n 个正整数，求两两 $\text{lcm}$lcm 的最大值。
所有输入在 $[1,10^5]$[1,105]范围内。

分析

首先枚举 $\gcd =g$gcd=g，那么将数组中 $g$g 的倍数都拿出来。
问题转化为，在数组中找两个互质的数，使他们的积尽量大。
我们将这些数从大到小枚举，那么枚举到一个数 $x$x 时，在已经枚举到的数中，如果有 $x,y$x,y 互质，那么对于所有 $z\in [x,y]$z∈[x,y] 的数，都不可能形成最终答案。所以可以维护一个栈，对于当前 $x$x，如果存在 $y$y 与 $x$x 互质，就弹掉 $x$x 到 $y$y 之间的数。
那怎么判断数组中是否有与 $x$x 互质的数？
记 $cn{t}_d$cntd​ 表示已经枚举的值中 $d$d 的倍数的个数， $tot$tot 表示与 $x$x 互质的数的个数。那么由容斥原理， $tot=\sum _{d\mid x}\mu \left(d\right)\times cn{t}_d$tot=d∣x∑​μ(d)×cntd​
然后每次入栈和弹栈，都用 ${\sigma }_0\left(x\right)$σ0​(x)（ $x$x 的约数个数） 的时间来更新 $cnt$cnt 数组。
总复杂度是 $O\left({\sum }_{i=1}^n{\sigma }_0\right(i{)}^2)$O(i=1∑n​σ0​(i)2) 的，大概是 $O\left(nlo{g}^{2}V\right)$O(nlog2V)
因为每个数作为倍数都入过 ${\sigma }_0\left(x\right)$σ0​(x) 次栈，每次入栈都要用 ${\sigma }_0\left(x\right)$σ0​(x) 来更新 $cnt$cnt 数组。

代码如下

#include <bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
vector<int> d[N];
int mu[N], v[N], q[N], p[N], x[N], cnt[N], tot, y, maxn = N - 5;
LL t, z = 1;
int get(int x){
	int i, ans = 0;
	for(i = 0; i < d[x].size(); i++) ans += mu[d[x][i]] * cnt[d[x][i]];
	return ans;
}
void update(int x, int v){
	int i;
	for(i = 0; i < d[x].size(); i++) cnt[d[x][i]] += v;
}
int main(){
	int i, j, n, m, c;
	LL ans = 0;
	mu[1] = 1;
	for(i = 2; i <= maxn; i++){
		if(!x[i]) x[i] = p[++tot] = i, mu[i] = -1;
		for(j = 1; j <= tot; j++){
			t = z * i * p[j];
			if(t > maxn) break;
			x[t] = p[j];
			if(i % p[j] == 0) break;
			mu[t] = -mu[i];
		}
	}
	for(i = 1; i <= maxn; i++)
		for(j = 1; j <= maxn / i; j++) d[i * j].push_back(i);
	scanf("%d", &n);
	for(i = 1; i <= n; i++){
		scanf("%d", &j);
		v[j] = 1;
		ans = max(ans, z * j);
	}
	for(i = 1; i <= maxn; i++){
		for(j = maxn / i; j >= 1; j--){
			if(!v[i * j]) continue;
			c = get(j);
			while(c){
				if(__gcd(q[y], j) == 1){
					ans = max(ans, z * i * j * q[y]);
					c--;
				}
				update(q[y], -1);
				y--;
			}
			q[++y] = j;
			update(j, 1);
		}
		while(y > 0) update(q[y], -1), y--;
	}
	printf("%lld", ans);
	return 0;
}