実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1180

問題概要

長さ $N$ の正整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられる。これから Anna と Bruno の2人がゲームを行う。このゲームは Anna を先手として交互に以下の操作を行う。

操作 : 任意の整数 $A_i$ に対して、 $A_i$ の正の約数であって $A_i$ 自身でないものを自由に選びそれを $x$ とする。その後、 $A_i$ を $x$ で置き換える。

先にこの操作を行えなくなった方が負けとなる。両者が勝ちを目指して最適な行動を取るとき、どちらが勝つか判定せよ。

制約

入力はすべて整数。
$1 \leq N \leq 10^5$
$2 \leq A_i \leq 10^5$

考察

このゲームの操作は以下のように言い換えることができる。

「任意の整数 $A_i$ に対して、その素因数 (重複を含む) を1つ以上選び、それらを削除する」

これは、 $N$ をコインの山の個数、 $A_i$ の重複を含む素因数の個数を $i$ 個目の山のコイン枚数とすることで、 Nim とよばれるゲーム問題に帰着することができる。

競プロにおけるゲーム問題や Nim についての話は以下の記事が詳しいので参照のこと。

algo-logic.info

Nim は必勝法が存在するゲームで、各山のコインの枚数の排他的論理和 (XOR) をとり、その和が $0$ ならば後手必勝、 $0$ でなければ先手必勝というように判定できる。

今回は $A_i$ の重複を含む素因数の個数を順次 XOR していくことになる。

計算量的には素因数分解の部分がボトルネックとなるが、 $A_i \leq 10^5$ なので愚直に行う $O(\sqrt{A_i})$ のやり方で十分。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    
    int x = 0;
    rep(i, 0, N) {
        int A;
        cin >> A;

        int cnt = 0;
        for (int j = 2; j * j <= A; j++) {
            while (A % j == 0) {
                A /= j;
                cnt++;
            }
        }

        if (A != 1) cnt++;

        x ^= cnt;
    }

    if (x == 0) cout << "Bruno" << endl;
    else cout << "Anna" << endl;
}