PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
1421
PREREQUISITES:
Observation
PROBLEM:
Alice and Bob play a game with an integer N, taking turns with Alice going first.
On their turn, a player must choose an odd prime factor of N, and subtract it from N.
Whoever cannot move loses.
Find the winner if both play optimally.
EXPLANATION:
Let’s get an edge case out of the way first: if N = 1, Alice cannot make a move at all and loses.
Now, let’s look at N\gt 1.
Let p be an odd prime factor of N.
Then, note that p is also an odd prime factor of N-p, since N is itself a multiple of p.
This allows Bob to win whenever N is even, by just copying Alice!
- If Alice doesn’t have any moves, she loses.
- Otherwise, Alice makes some move and N becomes N-p.
Now, since N is even and p is odd, we surely have N-p\gt 0 (since N-p will be odd). - From our earlier observation, p divides N-p so Bob can always make this move, leading to N-2p (which is even).
- This way, Bob can never lose: he can just copy Alice’s move at each step.
This also tells us that Alice can always win when N is odd (and greater than 1), since:
- If N is a prime, Bob will receive N-N=0 and lose.
- Otherwise, N being odd means N always has an odd prime factor p; and Bob will receive N-p which is even.
Now the roles are reversed: after the first move, Alice can copy Bob’s moves and never lose.
This gives us a straightforward solution: Alice wins if N is odd and \gt 1, Bob wins otherwise.
TIME COMPLEXITY
\mathcal{O}(1) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
print('Alice' if n%2 == 1 and n > 1 else 'Bob')