No.103 素因数ゲーム リターンズ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 126
作問者 : yuki2006yuki2006
1 ProblemId : 187 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:47:06

問題文

ちょっと前に素因数を習ったばかりの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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。