No.2 素因数ゲーム
yuki2006問題文
最近素因数を習ったばかりのAliceとBobが数字に関するゲームをします。
ゲームの内容は以下のとおりです。
・まず初めに、先攻のプレイヤーに\(2\)以上の自然数\(N\)が与えられます。
・その番のプレイヤーは、\(N\)に対して、「\(N\)の素因数」のどれかで割り、相手にその商になる数を渡します。
・この時、同じ数であれば、割り切れる限り１回以上であれば何回割ってもいいこととします。
例えば、\(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が勝つ方法があります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。