AGC010D: Decrementing

https://beta.atcoder.jp/contests/agc010/tasks/agc010_d

やっぱこういうのは偶奇ですね…。

操作を良く観察すると、奇数で割っても偶奇が変わらないことに気づきます。

なので列に奇数が2つ以上ある場合、または奇数が1つでもそれが1の場合、結局1ずつdecrementしていく作業と同じなので勝敗がわかります。

奇数が1つの場合はもう少し複雑で、どれか１つを偶数→奇数にして勝てるならそうして、それでも勝てなかったら奇数をdecrementしてA全体を最大公約数で割ります。この時2の階乗のみで割ると不十分なことに注意してください。
N=3,A={7,12,12}の時とか、7をdecrementして6ではなく2で割って、{3, 6, 6}にして考えると違う結果が出ます。それでWA出した。

ll gcd(ll a, ll b) {
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int N;
ll A[MAX_N];

bool sub_solve() {
	if(N == 1) return (A[0] - 1) % 2;
	bool second = false;
	while(true) {
		// debug(vi(A, A + N));
		int odd = 0;
		bool one = false;
		rep(i, 0, N) {
			if(A[i] % 2) odd++;
			if(A[i] == 1) one = true;
		}
		if((N - odd) % 2) return (second ^ 1);
		else if(odd != 1 || one) return second;
		else {
			if(A[0] % 2) A[0]--;
			ll g = A[0];
			rep(i, 0, N) {
				if(A[i] % 2) A[i]--;
				g = gcd(g, A[i]);
			}
			rep(i, 0, N) A[i] /= g;
		}
		second ^= 1;
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	if(sub_solve()) {
		cout << "First\n";
	}
	else cout << "Second\n";
}