题解

给定序列$a$，求$max{ lcm(a_i,a_j)}(n,a_i\leq 10^5)$

首先考虑将序列排序去重，并在过程中计算任意相等两数$lcm$的最大值

考虑枚举$gcd$的值，将所有$gcd$的倍数加入新序列内，问题转化为求序列中任意互质数对乘积的最大值

考虑维护一个栈，并将新序列中的元素从大到小依次加入，对于新加入的元素$x$，如果栈中存在$y$与其互质，那么栈中所有比$y$小的元素都可以删除，因为此时$x*y$一定大于接下来可能出现的答案$x’*y’$。($y’$是栈中比$y$小的数，而$x’$是接下来处理的元素，由于从大到小处理，所以$x’$一定小于$x$)所以当栈中存在与$x$互质的元素时，可以一直删除栈顶并更新答案

考虑如何查询栈中是否存在元素与$x$互质，设$cnt_d$表示栈中的元素有多少个是$d$的倍数，则经过简单的推导可知与$x$互质的数的个数为$\sum_{d|x} \mu(d)*cnt_d$。因此在栈中插入$x$与查询$x$的复杂度均为$O(d(i))$

以上两种算法结合，可以将判定是否存在互质对的问题转化为求最大乘积互质对的问题

因为每个数要入栈$d(i)$次，且每次入栈的复杂度小于$O(d(i))$，所以总复杂度为$O(\sum d(i)^2)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+1;

int n;
int a[N],u[N],cnt[N];
vector<int>g[N],d[N];
ll ans;

void prepare(){
	static bool vis[N];
	static int p[N];
	u[1]=1;
	for(int i=2;i<N;++i){
		if(!vis[i]){
			p[++p[0]]=i;
			u[i]=-1;
		}
		for(int j=1;j<=p[0]&&p[j]*i<N;++j){
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
			else u[i*p[j]]=-u[i];
		}
	}
	for(int i=1;i<N;++i)
	for(int j=1;i*j<N;++j)
	d[i*j].push_back(i);
}

void add(int x,int c){
	for(int i=0;i<d[x].size();++i){
		cnt[d[x][i]]+=c; 
	}
}

bool ask(int x){
	int ret=0;
	for(int i=0;i<d[x].size();++i){
		ret+=cnt[d[x][i]]*u[d[x][i]];
	}
	return ret>0;
}

int main(){
	prepare();
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<n;++i)
	if(a[i]==a[i+1]){
		ans=max(ans,(ll)a[i]);
	}
	n=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<d[a[i]].size();++j){
			int x=d[a[i]][j];
			g[x].push_back(a[i]/x);
		}
	}
	for(int i=1;i<N;++i){
		static int stack[N];
		static int top;
		while(top){
			add(stack[top--],-1);
		}
		for(int j=(int)g[i].size()-1;~j;--j){
			int x=g[i][j];
			while(top&&ask(x)){
				ans=max(ans,1ll*x*stack[top]*i);
				add(stack[top--],-1);
			}
			add(stack[++top]=x,1);
		}
	}
	cout<<ans<<endl;
}