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

Codeforces Round #201 (Div. 1) の練習会に参加しました。結果は AB 正解でそこそこです。よく考えたらこどふぉレートあげたいんだったら B 解けるかどうかで判断すれば良い気がしてきた。

問題

codeforces.com

解法

d を a[1] から a[n] の最大公約数とすると, 与えられた集合は最終的に d の倍数で埋められます。
つまり, a[1] から a[n] の中で最大の数を p*d とすると, 最終的に数の集合は
d, 2d, 3d, ..., pd
という形になります。よって, 結局施行する回数は一定で, p-n です。これの偶奇で勝敗が決まります。

const int MAXN = 111;
vector<int> a;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int g = 0;
    for (int i = 0; i < n; i++) g = __gcd(g, a[i]);
    a[n-1] /= g;
    if ((a[n-1]-n)%2 == 1) cout << "Alice" << endl;
    else cout << "Bob" << endl;
    return 0;
}