Codeforces #613 Div2 F. Classical?

CSAを思わせるシンプルな問題文。
http://codeforces.com/contest/1285/problem/F

問題

整数列Aが与えられる。
2要素のLCMのうち最大値を求めよ。

解法

同じ値の要素が2個以上ある場合、それらは解の候補となる。
以後、異なる2つの値のLCMを取ることを考える。
LCM(x,y)=x*y/GCD(x,y)なので、g=GCD(x,y)を満たす要素について考える。

Aのうちgの倍数となるものを、gで割って降順に並べた数列を考えよう。
ここで求めたいのは、この数列において互いに素な2要素のうち積の最大値である。そこにgを掛ければLCMの候補となる。
この手続きをスタックを使い求めて行く。
上記数列の先頭から処理していく。

スタック中dの倍数の要素数をC(d)とする。
次にスタックに積む数xに開始、スタック中でxと互いに素な要素の数は、xの約数dに対しsum(μ(d)*C(d))なので、互いに素な要素がある限りスタックを掘っていき、スタックの先頭の値とxを適宜比較していく。

int N;
int A[101010];
int cnt[101010],U[101010];
vector<int> D[101010];

int cop(int v) {
	int ret=0;
	FORR(d,D[v]) ret+=cnt[d]*U[d];
	return ret;
}

void add(int d,int v) {
	FORR(c,D[d]) cnt[c]+=v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100000;i++) {
		for(j=i;j<=100000;j+=i) D[j].push_back(i);
		
		if(i==1) U[i]=1;
		else if(i/D[i][1]%D[i][1]==0) U[i]=0;
		else U[i]-=U[i/D[i][1]];
	}
	
	ll ma=0;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		A[x]++;
		if(A[x]>=2) ma=max(ma,(ll)x);
	}
	for(i=1;i<=100000;i++) {
		vector<int> V;
		for(j=100000/i;j>0;j--) if(A[j*i]) {
			while(cop(j)) {
				if(__gcd(j,V.back())==1) ma=max(ma,1LL*j*V.back()*i);
				add(V.back(),-1);
				V.pop_back();
			}
			V.push_back(j);
			add(j,1);
		}
		FORR(v,V) add(v,-1);
	}
	cout<<ma<<endl;
	
}

まとめ

数列中で互いに素な2要素を求めるテクは今後使えるかも。