Game Theory in Competitive Programming Part 12

Codeforces: Deleting Divisors

Welcome to part 12 of this series, in case you have missed part 11, here is the link: Part 11

Problem Statement

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.

Problem Link

Problem - 1537D - Codeforces

Input

The first line contains a single integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

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

Output

For each test case output “Alice” if Alice will win the game or “Bob” if Bob will win if both players play optimally

Example

Input:

4

1

4

12

69

Output:

Bob

Alice

Alice

Bob

Explanation:

In the first test case, the game ends immediately because Alice cannot make a move so Bob wins.

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, making n=3. Then Bob cannot make a move, so Alice wins.

Hint:

Think about how will the game proceed optimally in the following different cases. When n is,

1. Odd
2. Even and not a power of two
3. Even and power of two.

Solution:

Case 1: When n is an odd number.

There are two possible sub-cases.

Sub-case 1: If n is a prime number, it is a losing state as there are no possible moves.

Sub-case 2: If n is odd and not a prime number, all its divisors must be odd. So, the only possible move is to subtract an odd divisor which will yield an Even number. Suppose the odd divisor is d. Since n is divisible by d, then n — d will also be divisible by d. After the move, an even number will be obtained that is not a power of 2 (Case 2).

Case 2: When n is an even number and not a power of two.

In this case, n must have at least one odd divisor. The optimal move will be to subtract that odd divisor, resulting in an odd number. By making this move, the opponent will always get an odd number which can either be a prime number (Opponent LOSES), or the opponent can make a move as described in Case 1 and return an even number that is not a power of 2. The process continues and you will never run out of moves because there will always be at least one odd divisor to subtract from n.

So, odd numbers are losing and even numbers that are not powers of two are a win.

Case 3: When n is a power of 2.

For this case, one possible move is to subtract a divisor such that the obtained number is even and not a power of 2 but this will be the winning position for the opponent. Hence, the optimal move is to make n half by subtracting n/2 such that it remains a power of 2. This process will continue till the number becomes 2.

So, if log2(n) is even, then player 1 wins otherwise player 2 wins.

Algorithm:

1. If the number n is odd (losing for player 1), Bob wins
2. Else, if the number n is not a power of 2 (winning for player 1), Alice wins.
3. Else, if the number n is a power of 2, and log2(n) is even, Alice wins.
4. Else, if the number n is a power of 2, and log2(n) is odd, Bob wins.

Source Code: