Submission #34819481

---

Source Code Expand

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 5;

int n;
int a[N];

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y); 
}

bool check() {
    i64 sum = 0;
    int evenCnt = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i] - 1;
        if (a[i] > 1 && a[i] % 2 == 1) {
            evenCnt++;
            pos = i;
        }
    }
    if (sum % 2 == 1) {
        return 1;
    } else if (evenCnt != 1) {
        return 0;
    }
    a[pos]--;

    int _gcd = a[1];
    for (int i = 2; i <= n; i++) {
        _gcd = gcd(_gcd, a[i]);
    }
    for (int i = 1; i <= n; i++) {
        a[i] /= _gcd;
    }
    return check() ^ 1;
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    if (check()) {
        printf("First\n");
    } else {
        printf("Second\n");
    }
    return 0; 
}

Submission Info

Judge Result