部内練習会。ししょーが5分で通してた。私は、まじかよって言いながら1時間かけて通した。 証明せずにとりあえず投げてみたら通った。

A. Alice and Bob

問題

正整数の集合が与えられる。ふたりのプレイヤーがいる。 集合から異なる2数を取ってきて、その差の絶対値を集合に加える(既に入っている場合はだめ)という操作を交互に繰り返す。 この操作を行なえなかったプレイヤーの負けである。最適に動いた場合の勝者を答えよ。

解法

どのような順で数を加えても結果は変わらないため、最終的にできる集合の大きさを答える問題と読み替えてよい。

初期の集合$X$の最大の数を$b$, 結果の集合$Y$に含まれる最小の数を$a$とすると$a = \gcd X$であり、結果の集合は$\{ a, 2a, 3a, \dots, b \}$である。

初期の集合$X$の各要素を$\gcd X$で割った集合$X’$の要素$x, y \in X’$を考える。 この$x, y$から始めてeuclid互除法を行なうと、$\gcd\{x, y\} = 1$であることから、$1$が作れることが分かる。 集合中に$1$が存在すれば、集合中の最大の数以下の全ての数を作ることができる。 よって、この結果を$X$に戻せば、結果の集合$Y$の最小の数$a = \gcd X$であり、$Y = \{ a, 2a, 3a, \dots, b \}$である。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b) {
    if (b <= a) swap(a,b);
    while (a) {
        ll a0 = a;
        a = b % a0;
        b = a0;
    }
    return b;
}
int main() {
    int n; cin >> n;
    vector<ll> a(n); repeat (i,n) cin >> a[i];
    ll d = a[0];
    repeat (i,n) d = gcd(d, a[i]);
    repeat (i,n) a[i] /= d;
    cout << (((*max_element(a.begin(), a.end()) - n) % 2) ? "Alice" : "Bob") << endl;
    return 0;
}