Codeforces Round #201 (Div. 1) A. Alice and Bob (R1600)

シンプルで楽しい感じ

問題へのリンク

問題概要

要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う

• 数列から 2 つの整数を選んで、その差を数列の末尾に追加する
• ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うことはできない

先に操作を行えなくなった方が負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

• 
• 

考えたこと

個の整数の最大公約数を として、 の倍数のうち の最大値以下のものはすべて作れる。逆にそれ以外は作れない。よって、

(その個数) - N

のパリティのみで勝敗が決まってしまう。戦略性は関係ない。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long GCD(long long x, long long y) {
    if (y == 0) return x;
    else return GCD(y, x % y);
}

int main() {
    int N; cin >> N;
    long long ma = 0, g = 0;
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        g = GCD(g, a);
        chmax(ma, a);
    }
    if ((ma/g - N) % 2 == 1) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}