枚举 \(\gcd\) ，对除 \(\gcd\) 后互质的数对求贡献。
从大到小枚举 \(a_i\) ，那么对于 \(x < z < y\) ，且 \((x,y)=1\) ，那么 \(z\) 和 \(y\) 都不会在余下的数中产生有价值的贡献。
那么维护一个栈，每个数只会进一次出一次。
为了保证复杂度，需要知道当前栈内是否有与 \(x\) 互质的数，莫反推推式子可以维护。
然后考虑去掉最外层的枚举。
对于两个数 \(x,y\) ，一定会有 \(a|x , b|y\) 使得 \(\operatorname{lcm}(a,b)=\operatorname{lcm}(x,y) , \gcd(a,b)=1\) ，
具体地，若 \(x\) 与 \(y\) 成倍数关系，将较小者变为 \(1\) 满足条件；若不成倍数关系，那么 \(a=\frac{x}{\gcd(x,y)} , b=y\) 符合条件。
所以只用保留 \(a_i\) 的所有倍数，答案与原问题一致。
需要预处理每个数的因子和去重。
复杂度 \(O(A \log A)\) 。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a[N],s[N],mu[N],pri[N],cnt;
ll ans;
vector<int> fac[N];
bool bz[N],bz1[N];
stack<int> q;
void init(int n){
mu[1]=1;
fo(i,2,n){
if(!bz[i])pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt && i*pri[j]<=n;++j){
bz[i*pri[j]]=1;
if(!(i%pri[j])){
// mu[i*pri[j]]=0;
break;
}
mu[i*pri[j]]=-mu[i];
}
}
fo(i,1,n)
for(int j=i;j<=n;j+=i)fac[j].push_back(i);
}
int main(){
scanf("%d",&n);
fo(i,1,n)scanf("%d",&a[i]);
sort(a+1,a+n+1);
init(N-10);
fo(i,1,n)if(a[i]!=a[i-1])
for(auto x:fac[a[i]])bz1[x]=1;
n=0;
fd(i,N-10,1)if(bz1[i])a[++n]=i;
ans=1;
fo(i,1,n){
int v=0;
for(auto x:fac[a[i]])v+=mu[x] * s[x];
if(v){
while(v){
int x=q.top();q.pop();
if(__gcd(a[i],x)==1)ans=max(ans , (ll)a[i]*x);
for(auto y:fac[x]){
--s[y];
if(!(a[i]%y))v-=mu[y];
}
}
}
q.push(a[i]);
for(auto x:fac[a[i]])++s[x];
}
printf("%lld\n",ans);
return 0;
}