No.2 素因数ゲーム

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 195
作問者 : yuki2006yuki2006

3 ProblemId : 18 / 出題時の順位表

問題文

最近素因数を習ったばかりのAliceとBobが数字に関するゲームをします。

ゲームの内容は以下のとおりです。
・まず初めに、先攻のプレイヤーに\(2\)以上の自然数\(N\)が与えられます。
・その番のプレイヤーは、\(N\)に対して、「\(N\)の素因数」のどれかで割り、相手にその数を渡します。
・この時、同じ数であれば、割り切れる限り1回以上であれば何回割ってもいいこととします。
例えば、\(24\)の素因数は \(2,3\ (24 = 2 \times 2 \times 2 \times 3) \) であるため \(24\)を\(2\)で\(2\)回わった数\(6\)を相手に渡すことが出来ます。
・次のプレイヤーは渡された数を新たな\(N\)とし、以上の手順を繰り返します。
・渡された数が\(1\)になったプレイヤーが負けです。

まずAliceが先攻となりゲームを始めます。
この時、どちらも最善を尽くすと考えたとき、自然数\(N\)が与えられた時の勝者を求めてください。

入力

N

\( 2 \leq N \leq 100,000,000 \)

出力

勝者のプレイヤーの文字列を1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4
出力
Alice

Aliceは\(4\)を、素因数である\(2\)で\(2\)回割ってBobに渡します。するとBobは\(1\)を受け取ることになり Bobの負けです。

サンプル2
入力
11
出力
Alice

Aliceは素因数である\(11\)で割って、Bobに渡せるのでAliceの勝ちが決定しています。

サンプル3
入力
24
出力
Alice

Aliceは\(24\)を\(2^2\)で割ることにより\(6\)をBobに渡します。
Bobはそれを\(2\)または\(3\)で割ります。
Aliceは\(2\)または\(3\)が渡されるので、どちらも素因数なのでそれで割るとBobに\(1\)が渡り、Aliceの勝ちになります。

サンプル4
入力
600
出力
Bob

実はAliceがどう割ってもBobが勝つ方法があります。

提出ページヘ