F - Classical?
考虑先加上\(gcd(a_i,a_j)=1\)的限制
从大到小扫集合里的数，若扫到数\(x\)发现存在\(y>x\)且\(gcd(x,y)=1\)，则所有\(x<t<y\)的\(t\)都不会再对答案有贡献了，因此使用栈存储扫过的元素，当扫到\(x\)时，只要栈中有与\(x\)互质的数就弹栈，并与\(x\)更新答案
那么如何快速判断集合中有与\(x\)互素的数？莫反！\(y\)是集合中的数，\(cnt[i]\)表示集合中\(i\)的倍数的个数
\[\sum_{i|gcd(x,y)}\mu(i)=\sum_{i|x,i|y}\mu(i)=\sum_{i|x}\mu(i)cnt[i]
\]
这个过程的复杂度是\(O(A\log A)\)的
接下来也可以枚举\(gcd(a_i,a_j)=g\)，并对所有\(g\)的倍数执行上述过程，时间复杂度\(O(A(\log A)^2)\)
更巧妙的做法是把每个\(a_i\)的所有因数加入集合。若原始的答案为\(lcm(a,b)\)，那么其也一定可以被表述为\(x\times y\)（\(x|a,y|b\)），时间复杂度就是\(O(A\log A)\)的
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,mu[N],maxa,cnt[N];
ll ans;
vector<int> q;
bool vis[N];
vector<int> factor[N];
int main(){
scanf("%d",&n);
for(int i=1,a;i<=n;++i) scanf("%d",&a),maxa=max(maxa,a),vis[a]=true;
ans=maxa,mu[1]=1;
for(int i=1;i<=maxa;++i)
for(int j=i<<1;j<=maxa;j+=i)
mu[j]-=mu[i];
for(int i=1;i<=maxa;++i)
for(int j=i;j<=maxa;j+=i){
if(mu[i]!=0) factor[j].pb(i);
vis[i]|=vis[j];
}
for(int i=maxa,num=0;i;--i,num=0){
if(!vis[i]) continue;
for(auto j:factor[i]) num+=mu[j]*cnt[j];
while(num>0){
int las=num;
for(auto j:factor[q.back()]){
--cnt[j];
if(i%j==0) num-=mu[j];
}
if(las!=num) ans=max(ans,1ll*i*q.back());
q.pop_back();
}
for(auto j:factor[i]) ++cnt[j];
q.pb(i);
}
printf("%lld",ans);
return 0;
}