[cf1285F]Classical

先枚举$d=gcd$，然后暴力枚举所有$d$的倍数，相当于求出若干个数中最大的互素对

假设选出的数依从大到小排序后为$a_{i}$，令$g_{i}=min_{(a_{i},a_{j})=1}j$，则答案为$max a_{i}cdot a_{g_{i}}$

考虑一种比较奇怪的计算$g_{i}$的方式，先求出$tot=sum_{j=1}^{n}[(a_{i},a_{j})=1]$，然后从$n$到1依次删除，直到删除的数中与$a_{i}$互素的数达到了$tot$个

关于$tot$的计算可以用莫比乌斯反演，即化简为$sum_{d|a_{i}}mu(d)sum_{j=1}^{n}[d|a_{j}]$，记后面的式子为$f(d)$，可以在插入$a_{j}$时处理，那么就可以做到”均摊“单次插入/删除/询问$o(ln n)$

之后考虑从$n$到1依次去删除，复杂度为$o(n-g_{i})$，但注意到若$g_{i}ge g_{i-1}$那么没有意义，因此从$g_{i-1}$开始统计（即令$n=g_{i-1}$）就可以做到$o(nln^{2}n)$了（枚举$d$+计算$tot$的调和级数和gcd）

#include<bits/stdc++.h>
using namespace std;
#define N 100005
vector<int>v,d[N];
int n,x,vis[N],mu[N],p[N],f[N];
long long ans;
int gcd(int x,int y){
    if (!y)return x;
    return gcd(y,x%y);
}
void update(int k,int p){
    for(int i=0;i<d[k].size();i++)f[d[k][i]]+=p;
}
int query(int k){
    int ans=0;
    for(int i=0;i<d[k].size();i++)ans+=mu[d[k][i]]*f[d[k][i]];
    return ans;
}
int main(){
    mu[1]=1;
    for(int i=2;i<N-4;i++){
        if (!vis[i]){
            p[++p[0]]=i;
            mu[i]=-1;
        }
        for(int j=1;(j<=p[0])&&(i*p[j]<N-4);j++){
            vis[i*p[j]]=1;
            if (i%p[j])mu[i*p[j]]=-mu[i];
            else{
                mu[i*p[j]]=0;
                break;
            } 
        }
    }
    scanf("%d",&n);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        vis[x]=1;
    }
    for(int i=1;i<N-4;i++)
        for(int j=i;j<N-4;j+=i)d[j].push_back(i);
    for(int i=1;i<N-4;i++){
        v.clear();
        for(int j=i;j<N-4;j+=i)
            if (vis[j])v.push_back(j/i);
        int m=v.size();
        for(int j=0;j<m;j++)update(v[j],1);
        for(int j=m-1,k=0;j>=0;j--){
            int sum=query(v[j]);
            while (sum){
                if (gcd(v[j],v[k])==1){
                    sum--;
                    ans=max(ans,1LL*v[j]*v[k]*i);
                }
                update(v[k++],-1);
            }
            if (!j)
                while (k<m)update(v[k++],-1);
        }
    }
    printf("%lld",ans);
}