一目見て惹かれた。すごく面白かった。割と自然な考察の流れで解けた。

問題概要

$N$ 個の正の整数からなる数列 $A_1, A_2, \dots, A_N$ が与えられる。先手と後手が交互に以下を繰り返す。先に操作を行えなくなった方が負けである。双方最善を尽くしたときにどちらが勝つか？

$2$ 以上の整数を 1 つ選んで、1 減らす。その後 $N$ 個の整数の最大公約数を $g$ として、各整数を $g$ で割る

制約

$1 \le N \le 10^{5}$
初期状態では $N$ 個の整数の最大公約数は $1$

考えたこと

面白そう！！！
こういうのは小さいケースで具体的に手を動かしてみると自然に解ける気がする。

$N=1$ のとき、 $A_1 = 1$ だったら負け、 $A_1 > 1$ だったら勝ち

$N=2$ のとき、 $(1, A)$ の形だったら、 $A-1$ が偶数だったら負け、奇数だったら勝ち、というのはすぐにわかる。また同時に、 $A$ の中に 1 個でも 1 があったら、そこから先は最大公約数はかならず 1 なので、残りの $A_i - 1$ の総和のパリティのみで決まってしまう。

ここまで考えてみると、パリティの考察が大事な問題に思えて来る。最大公約数が偶数か奇数かが結構命運を分けるように思える。

最大公約数が奇数のとき、元々奇数だったものは奇数に、偶数だったものは偶数になることから、最大公約数で割ることによって $A_i - 1$ の総和のパリティは変化しないことがわかる！！！

つまり、もし $A_i - 1$ の総和のパリティが奇数の盤面が与えられた状態から、相手に

$A_i - 1$ の総和のパリティが偶数
$A_i$ の中に奇数が 2 個以上ある

という盤面を渡せたならば、相手はどうやっても最大公約数が奇数になる手しか打てないので、こちらにはまた総和のパリティが奇数の盤面が渡って来るので、これを繰り返して勝ち確になる。この対称戦略がこのゲームの肝になりそう。

詰める

いよいよここから詰める！！！
まず $A_i$ の中に 1 がある場合は勝敗が決まっているので、1 はないものとする。また、すべて偶数ということはありえない (最大公約数が 1 なため) ので、奇数は 1 個以上含まれる。

奇数が 2 個のとき

比較的明快。

$A_i - 1$ の総和が奇数のとき、相手に「奇数が 1 個だけ」という盤面を与えないように注意すれば、勝ち確定
$A_i - 1$ の総和が偶数のとき、どうやっても最大公約数が奇数にしかできないので、負け確定

奇数が 1 個のとき

$A_i - 1$ の総和が奇数のときは簡単。相手に「奇数が 1 個だけ」という盤面を与えないように注意すれば勝ち確定。

問題は $A_i - 1$ の総和が偶数のとき。
しかしよく考えると、このときに打てる手はもう

$A_i - 1$ が奇数となっている部分を 1 減らして、最大公約数を偶数にする

しか勝ち目がないことがわかる。それ以外の手はすべて相手勝ちになるからだ。つまりこの問題は

選べる手が実質的に1通りしかない

ということになる。よって再帰的に Greedy に手を打っていくことで勝敗が確定する。

#include <iostream>
#include <vector>
using namespace std;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }

bool solve(vector<int> A) {
    long long sum = 0;
    int odd = 0;
    bool ichi = false;
    for (int i = 0; i < A.size(); ++i) {
        sum += A[i] - 1;
        if (A[i] & 1) ++odd;
        if (A[i] == 1) ichi = true;
    }
    if (ichi) {
        if (sum % 2 == 0) return false;
        else return true;
    }
    else if (odd > 1) {
        if (sum % 2 == 0) return false;
        else return true;
    }
    else {
        if (sum % 2 == 1) return true;
        for (int i = 0; i < A.size(); ++i) if (A[i] & 1) --A[i];
        long long g = A[0];
        for (int i = 0; i < A.size(); ++i) g = GCD(g, A[i]);
        for (int i = 0; i < A.size(); ++i) A[i] /= g;
        if (!solve(A)) return true;
        else return false;
    }
}

int main() {
    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    if (solve(A)) puts("First");
    else puts("Second");
}