TopCoder SRM 743 Div1 Easy, Div2 Hard MaximizingGCD

Easy/Medium早解きでレート微増をキープ。
https://community.topcoder.com/stat?c=problem_statement&pm=15211

問題

偶数個の要素からなるの整数集合S[i]が与えられる。
これらを２個ずつペアにして、それらの和からなる集合を構築したとき、全要素のGCDの最大値は何か。

解法

S[0]とペアにするS[i]を総当たりしてみる。
するとGCDの候補gは(S[0]+S[i])の約数になる。

GCDの候補gが決まれた、S中でS[0]とS[i]を除くS[j]をmod gで分類することで、全ペアの和がgの倍数になるかどうか容易に判定できる。

class MaximizingGCD {
	public:
	int maximumGCDPairing(vector <int> A) {
		int N=A.size();
		ll ma=0;
		int i,j;
		for(i=1;i<N;i++) {
			ll sum=A[0]+A[i];
			vector<ll> C;
			for(ll x=1;x*x<=sum;x++) if(sum%x==0) {
				C.push_back(x);
				C.push_back(sum/x);
			}
			
			FORR(c,C) {
				multiset<ll> M;
				for(j=1;j<N;j++) if(j!=i) {
					ll a=A[j]%c;
					if(M.count((c-a)%c)) M.erase(M.find((c-a)%c));
					else M.insert(a);
				}
				if(M.empty()) ma=max(ma,c);
			}
		}
		return ma;
	}
}

まとめ

(S[i]+S[j])を列挙してる人がいて、Challengeしようと思ったけど危なそうなのでやめておいた。