# FIZZBUZZ2305 - Editorial

Authors: naisheel, jalp1428
Tester: tabr
Editorialist: iceknight1093

1421

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')

3 Likes

can any one simplify the observation