No.103 素因数ゲーム リターンズ
yuki2006問題文
ちょっと前に素因数を習ったばかりのAliceとBobが再び数字に関するゲームをします。
ゲームの内容は以下のとおりです。
・$N$個の整数が与えられます。$M_1\ M_2\ \dots M_i \dots \ M_N$と表します。
・その番のプレイヤーは、$N$個の整数のうち、$i$番目の数字を選び「\(M_i \)の素因数」のどれかで割り、$i$番目の数をその商で更新します。
・この時、同じ素因数であれば、割り切れる限り1回以上、$2$回まで割ることができます。
例えば、$i$番目の値が\(24\)だった場合、その素因数は \(2,3\ (24 = 2 \times 2 \times 2 \times 3) \) であるため \(24\)を\(2\)で\(2\)回割った数の\(6\)に更新することができます。
・以上の手順をプレイヤーを入れ替え繰り返し、$N$個のすべての数を\(1\)にしたプレイヤーが勝ちです。
まずAliceが先攻となりゲームを始めます。
この時、どちらも最善を尽くすと考えたとき、$N$個の整数が与えられた時の勝者を求めてください。
入力
$N$ $M_1\ M_2\ \dots M_i \dots \ M_N$
入力は全て整数で与えられる。
\( 1 \leq N \leq 100 \)
\( 2 \leq M_i \leq 10,000=10^4 \)
出力
勝者のプレイヤー「Alice」または「Bob」の文字列を1行で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 4
出力
Alice
Aliceは\(4\)を、素因数である\(2\)を$2$回割って、$1$に更新します。
この時点でAliceの勝利です。
サンプル2
入力
2 11 19
出力
Bob
$11$も$19$も、素数であるため、Bobが勝利します。
サンプル3
入力
1 24
出力
Alice
Aliceは\(24\)を\(2^2\)で割ることにより\(6\)に更新します。
Bobはそれを\(2\)または\(3\)で割ります。
Aliceは\(2\)または\(3\)になっている値を、どちらも素因数なのでそれで割るとすべて1になるので、Aliceの勝ちになります。
サンプル4
入力
4 600 1200 1800 2400
出力
Bob
実はAliceがどう割ってもBobが勝つ方法があります。
サンプル5
入力
2 6 23
出力
Alice
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。