Codeforces #552: Div3. G. Minimum Possible LCM

中盤えらく手間取ってる回。
https://codeforces.com/contest/1154/problem/G

問題

整数列Aが与えられる。
Aの２要素の対のうち、そのLCMが最小値となるものの１例を示せ。

解法

GCDの値を総当たりしよう。
GCDの値の倍数となる要素のうち、小さい２要素の対が解の候補となる。

int N;
int C[10101011];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(C);
	ll mi=1LL<<60;
	int L=-1,R=-1;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		if(C[x]>=0) {
			if(x<mi) {
				mi=x;
				L=i;
				R=C[x];
			}
		}
		else {
			C[x]=i;
		}
	}
	
	for(i=1;i<=10000000;i++) {
		int id=-1;
		ll v=-1;
		for(j=i;j<=10000000;j+=i) {
			if(C[j]>=0) {
				if(v>=0) {
					ll cand=v/i*j;
					if(cand<mi) {
						mi=cand;
						L=id;
						R=C[j];
					}
					break;
				}
				id=C[j];
				v=j;
			}
		}
	}
	if(L>R) swap(L,R);
	cout<<L+1<<" "<<R+1<<endl;
}

まとめ

G問題自体はかなりあっさり解けてるんだけどな。