Deleting Divisors
Contest: Codeforces Round 726 (Div. 2)
Difficulty rating: 1700
Tags: games, math, number theory

Alice and Bob are playing a game.

They start with a positive integer $$$n$$$ and take alternating turns doing operations on it. Each turn a player can subtract from $$$n$$$ one of its divisors that isn't $$$1$$$ or $$$n$$$. The player who cannot make a move on his/her turn loses. Alice always moves first.

Note that they subtract a divisor of the current number in each turn.

You are asked to find out who will win the game if both players play optimally.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the initial number.

Output format:
For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the game ends immediately because Alice cannot make a move.

In the second test case, Alice can subtract $$$2$$$ making $$$n = 2$$$, then Bob cannot make a move so Alice wins.

In the third test case, Alice can subtract $$$3$$$ so that $$$n = 9$$$. Bob's only move is to subtract $$$3$$$ and make $$$n = 6$$$. Now, Alice can subtract $$$3$$$ again and $$$n = 3$$$. Then Bob cannot make a move, so Alice wins.

Example input:
4
1
4
12
69

Example output:
Bob
Alice
Alice
Bob

Editorial:
Let's consider $$$3$$$ cases for this problem:
1) n is odd
2) n is even, and $$$n$$$ is not a power of $$$2$$$
3) n is a power of $$$2$$$
If $$$n$$$ is odd, the only move is to subtract an odd divisor (since all the divisors are odd). Doing this, we will obtain an even number that is not a power of $$$2$$$(case 2). If $$$D$$$ is the divisor of $$$n$$$, then $$$n-D$$$ must also be divisible by $$$D$$$, and since $$$D$$$ is odd, $$$n-D$$$ cannot be a power of $$$2$$$.
If $$$n$$$ is even and is not a power of $$$2$$$, it means that $$$n$$$ has an odd divisor. By subtracting this odd divisor, we will obtain $$$n-D$$$ is odd(case 1). Now let's show that subtracting an odd divisor every move results in a win. Primes are losing since the only move you can make on them is subtracting the entire number, which results in $$$n = 0$$$ and a loss. Since every prime is odd or a power of 2, it works to give the other player an odd number because it will either be a prime(the other player loses), or they will make a move and give you another even number that is not a power of 2. You can continue this process because you will never land on a losing number and because the game must end after a finite number of moves, your opponent must always lose.
So we proved that odd numbers are losing and even numbers that are not powers of $$$2$$$ are winning.
What if $$$n$$$ is a power of $$$2$$$? You can do two things in one move, halve $$$n$$$ or make n an even number that is not a power of $$$2$$$(we proved that this is a winning position for the other player). The only optimal move is to halve $$$n$$$, making it another power of $$$2$$$. The players continue like this until one gets $$$2$$$, which is a prime number, so it's losing. If $$$log_2(n)$$$ is even, Alice wins, otherwise Bob wins.