CF1285F Classical?

首先一个很自然的想法就是枚举钦定\(\gcd(a_i,a_j)\)的值为\(d\)，然后再枚举所有\(d\)的倍数，钦定它们之间的\(\gcd=d\)时才统计贡献

但这样本身浪费了不少时间在重复的枚举上，不妨换个思路，我们直接预先将每个数所有的约数都放入一个集合\(S\)

显然\(|S|\le 10^5\)，而我们此时可以把条件收紧为钦定每次选出的两个数\(x,y\)必须互质，此时的贡献就是\(x\times y\)

考虑从大到小处理所有的数，假设现在扫到了数\(x\)且之前存在某个数\(y>x\)满足\(\gcd(x,y)=1\)，则所有\(z\in(x,y)\)的数显然都不会对答案造成贡献了，可以直接删去

因此可以用一个栈来存储之前被扫过的元素，当遇到一个数\(x\)时，只要栈中存在和\(x\)互质的数就弹栈并更新答案

只要我们能快速确定栈中有没有和\(x\)互质的元素，这个做法的复杂度就是有保证的，因为每个数只会被加入/删除一次

不妨设\(c(i)\)表示数\(i\)是否在栈中，令\(f(x)=\sum_i c(i)\times[\gcd(i,x)=1]\)，则每次只需判断\(f(x)\)的值是否大于\(0\)即可

而对于\(f(x)\)显然可以用莫比乌斯反演处理一下：

令\(g(i)=\sum_{i|j} c(j)\)，则\(f(x)=\sum_{d|x} \mu(d)\times g(d)\)

每次求一遍\(f(x)\)和更新\(g(i)\)的复杂度都是约数个数级别的，因此总复杂度为\(O(A\log A)\)（其中\(A\)为数的值域）

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e5+5;
int n,m,a[N],c[N],ext[N],pri[N],cnt,vis[N],mu[N],stk[N],top;
vector <int> frac[N]; long long ans=1;
inline void init(CI n)
{
	RI i,j; for (mu[1]=1,i=2;i<=n;++i)
	{
		if (!vis[i]) pri[++cnt]=i,mu[i]=-1;
		for (j=1;j<=cnt&&i*pri[j]<=n;++j)
		{
			vis[i*pri[j]]=1; 
			if (i%pri[j]==0) break; else mu[i*pri[j]]=-mu[i];
		}
	}
	for (i=1;i<=n;++i) for (j=i;j<=n;j+=i) frac[j].push_back(i);
}
signed main()
{
	RI i; for (scanf("%lld",&n),init(1e5),i=1;i<=n;++i)
	{
		scanf("%lld",&a[i]); m=max(m,a[i]);
		for (auto x:frac[a[i]]) c[x]=c[a[i]/x]=1;
	}
	for (i=m;i>=1;--i) if (c[i])
	{
		int ret=0; for (auto x:frac[i]) ret+=mu[x]*ext[x];
		auto work=[&](CI x,CI opt)
		{
			for (auto y:frac[x])
			if (ext[y]+=opt,opt==-1)
			if (i%y==0) ret-=mu[y];
		};
		while (ret>0)
		{
			work(stk[top],-1);
			ans=max(ans,1LL*i*stk[top--]);
		}
		stk[++top]=i; work(i,1);
	}
	return printf("%lld",ans),0;
}