Codeforces #879 : Div2 E. MEX of LCM

コードは短め。
https://codeforces.com/contest/1834/problem/E

問題

N要素の整数列Aが与えられる。
Aの部分列のLCMを並べたときのMex値を求めよ。

解法

Aの部分列の数を考えると、Mex値は高々O(N^2)である。
そこでAの部分列のLCMのうち、N^2以下のものを列挙すればよい。

int T,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> A,B,C;
		int ma=3*N;
		FOR(i,N) {
			cin>>x;
			
			if(x<=ma) B.insert(x);
			FORR(a,A) {
				ll b=1LL*a*x/gcd(a,x);
				if(b<ma) B.insert(b);
			}
			FORR(b,B) C.insert(b);
			swap(A,B);
			B.clear();
		}
		x=1;
		while(C.count(x)) x++;
		cout<<x<<endl;
		
	}
}

まとめ

考察が済めば簡単だけど、本番に確信持ってこの方式で行けるかな…。