CF1285F Classical?解题报告

解题报告

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$）

分析

$\text{lcm}$ 并不好处理，考虑枚举 $a_i,a_j$ 的 $\gcd$（设其为 $g$），取出满足条件的数（即 $g$ 的倍数），那么我们要求的就是 $\gcd$ 为 $g$ 的数对乘积最大值了。

我们发现取出所有数的复杂度是 $O(\sum\lfloor\frac{n}{i}\rfloor)=O(n\log n)$时间的，所以我们可以直接取出所有数来判断。

我们将取出来的所有数除以 $g$，那么数对的 $\gcd$ 为 $1$，从大到小扫，设扫到了 $x$，如果之前有与它互素的数，那么仅有最大的那个数有用，且与它互素的数在后面一定没有用了。

这是一个很好的性质，考虑扫的时候怎么快速判断是否存在与它互素的数：

与它互素的数实在太多了，无法逐一枚举，但是所有数的因子总数却只有 $O(n\log n)$ 级别，于是我们考虑每次只枚举每个数的因子。

具体地，我们发现可以容斥计算与 $x$ 互素的数个数：（设 $tot_i$ 表示 $i$ 的倍数出现次数）

加入一个数和删除一个数暴力算贡献，判断的时候就直接查，然后弹栈，这样的复杂度为 $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;
}