题解 CF1285F【Classical?】
whiteqwq
·
·
题解
CF1285F Classical?解题报告：
更好的阅读体验
题意
给定 n 个数，a_{1\cdots n}，求 \max\{\text{lcm}(a_i,a_j)\mid1\leqslant i,j\leqslant n\}。（1\leqslant n,a_i\leqslant 10^5）
分析
我们发现取出所有数的复杂度是 $O(\sum\lfloor\frac{n}{i}\rfloor)=O(n\log n)$ 时间的，所以我们可以直接取出所有数来判断。
我们将取出来的所有数除以 $g$，那么数对的 $\gcd$ 为 $1$，从大到小扫，设扫到了 $x$，如果之前有与它互素的数，那么仅有最大的那个数有用，且与它互素的数在后面一定没有用了。
这是一个很好的性质，考虑扫的时候怎么快速判断是否存在与它互素的数：
与它互素的数实在太多了，无法逐一枚举，但是所有数的因子总数却只有 $O(n\log n)$ 级别，于是我们考虑每次只枚举每个数的因子。
具体地，我们发现可以容斥计算与 $x$ 互素的数个数：（设 $tot_i$ 表示 $i$ 的倍数出现次数）
$$\sum_{d\mid x} \mu_dcnt_d$$
加入一个数和删除一个数暴力算贡献，判断的时候就直接查，然后弹栈，这样的复杂度为 $O(n\log^2 n)$。
能不能再给力一点呢？
我们发现刚刚的方法只能处理 $\gcd=1$ 的情况，那么我们可以取出所有数的因子加入序列中，对于 $\text{lcm}$ 最大的数对 $(x,y)$，它们的两个因子 $x'=\frac{x}{\gcd(x,y)},y'=y$，满足 $\text{lcm}(x,y)=\text{lcm}(x',y')$，于是一定存在两个互素的数 $\text{lcm}$ 仍为最大值。
时间复杂度：$O(n\log n)$。（默认 $n$ 与值域同阶）
## 代码
```
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100005;
int n,maxx,top;
int a[maxn],ok[maxn],cnt[maxn],miu[maxn],stk[maxn];
long long ans;
vector<int>d[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),ok[a[i]]=1,maxx=max(maxx,a[i]);
ans=maxx,miu[1]=1;
for(int i=1;i<=maxx;i++){
for(int j=2*i;j<=maxx;j+=i){
miu[j]-=miu[i],d[j].push_back(i);
if(ok[j])
ok[i]=1;
}
d[i].push_back(i);
}
for(int i=maxx;i>=1;i--){
if(ok[i]==0)
continue;
int sum=0;
for(int j=0;j<d[i].size();j++)
sum+=miu[d[i][j]]*cnt[d[i][j]];
while(sum>0){
int dec=0;
for(int j=0;j<d[stk[top]].size();j++){
cnt[d[stk[top]][j]]--;
if(i%d[stk[top]][j]==0)
dec+=miu[d[stk[top]][j]];
}
if(dec)
sum-=dec,ans=max(ans,1ll*i*stk[top]);
top--;
}
for(int j=0;j<d[i].size();j++)
cnt[d[i][j]]++;
stk[++top]=i;
}
printf("%lld\n",ans);
return 0;
}
```