No.2 Prime Factor Game
タグ : / 解いたユーザー数 698
作問者 :
Problem Statement
Alice and Bob, who have only recently learned about prime factors, play a game involving numbers.
The rules of the game are as follows.
・First, the player who moves first is given a natural number \(N\) of at least \(2\).
・The player whose turn it is divides \(N\) by one of the "prime factors of \(N\)" and passes the resulting quotient to the opponent.
・At this time, the player may divide by the same number any number of times, as long as it is at least once and the number remains divisible.
For example, the prime factors of \(24\) are \(2,3\ (24 = 2 \times 2 \times 2 \times 3) \), so the player can divide \(24\) by \(2\) \(2\) times and pass the resulting number \(6\) to the opponent.
・The next player takes the received number as the new \(N\) and repeats the above procedure.
・The player who receives the number \(1\) loses.
Alice moves first and starts the game.
Assuming both players play optimally, determine the winner when the natural number \(N\) is given.
Input
N
\( 2 \leq N \leq 100,000,000 \)
Output
Print the string of the winning player on one line.
Print a newline at the end.
Sample
Sample 1
Input
4
Output
Alice
Alice divides \(4\) by its prime factor \(2\) \(2\) times and passes the result to Bob. Bob then receives \(1\), so Bob loses.
Sample 2
Input
11
Output
Alice
Alice can divide by the prime factor \(11\) and pass the result to Bob, so Alice's win is decided.
Sample 3
Input
24
Output
Alice
Alice divides \(24\) by \(2^2\) and passes \(6\) to Bob.
Bob divides it by \(2\) or \(3\).
Alice is then passed \(2\) or \(3\). Since either one is a prime factor of itself, dividing by it passes \(1\) to Bob, and Alice wins.
Sample 4
Input
600
Output
Bob
In fact, no matter how Alice divides, Bob has a way to win.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。