Codeforces

Luogu

分析

下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。

考虑枚举答案的 $\gcd$，问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。

可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序，然后依次扫描，同时开一个栈来维护。对于每个数，我们需要判断栈中有没有与它互质的数，假设有 $s$ 个，则我们一直弹栈，直到弹出 $s$ 个与它互质的数，并在弹栈过程中更新答案即可。

一个关于正确性的感性理解：因为之后加进来的都比当前的小，弹出去的都比当前更新答案的小，所以弹出去的所有数不会影响答案。

现在的问题就是如何求栈中和某个数互质的数的个数。设栈中有 $c_i$ 个 $i$，则栈中与 $x$ 互质的数的个数为
$$
\sum_{i=1}^{A}c_i[\gcd(i,x)=1]
$$
莫比乌斯反演得到
$$
\sum_{d|x}\mu(d)\sum_{d|i,i\leq A}c_i
$$
于是我们只需要入栈、出栈时维护每个数有多少个倍数在栈中即可。

总时间复杂度大概是 $\mathcal{O}(A\log^2 A)$。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,lim,a[N],vis[N];
vector<int> vec,d[N];
int cnt[N],sta[N],top;
int p[N],v[N],mu[N],pcnt=0;

void sieve(int n) {
    mu[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++pcnt]=i,mu[i]=-1;
        for (int j=1;j<=pcnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else break;
        }
    }
    for (int i=1;i<=n;++i)
        for (int j=i;j<=n;j+=i)
            d[j].push_back(i);
}

int main() { sieve(1e5);
    n=read();
    for (int i=1;i<=n;++i)
        a[i]=read(),lim=max(lim,a[i]),++vis[a[i]];
    ll ans=0;
    for (int g=1;g<=lim;++g) {
        vec.clear();
        for (int i=g;i<=lim;i+=g)
            for (int j=1;j<=vis[i];++j) vec.push_back(i/g);
        sort(vec.begin(),vec.end(),greater<int>());
        for (int i:vec) {
            int s=0;
            for (int j:d[i]) s+=mu[j]*cnt[j];
            while (s) {
                int x=sta[top--];
                if (__gcd(i,x)==1) ans=max(ans,1ll*g*i*x),--s;
                for (int j:d[x]) --cnt[j];
            }
            sta[++top]=i;
            for (int j:d[i]) ++cnt[j];
        }
        while (top) {
            int x=sta[top--];
            for (int i:d[x]) --cnt[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}