Deleting Divisors (Codeforces 1537D)
Tags: Math, games

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: 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: For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

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.

Sample Inputs:
4
1
4
12
69

Sample Outputs:
Bob
Alice
Alice
Bob

Solution (Python):
import math
cases = []
for _ in range(int(input())):
    cases.append(int(input()))
for case in cases:
    if math.log2(case) % 1 == 0 and math.log2(case) % 2 == 1:
        print('Bob')
    elif case % 2 == 1:
        print('Bob')
    else:
        print('Alice')

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    if n == 1:
        return 'Bob'
    cnt = 0
    v = n
    while v % 2 == 0:
        v //= 2
        cnt += 1
    if v > 1:
        return 'Alice' if cnt > 0 else 'Bob'
    else:
        return 'Alice' if cnt % 2 == 0 else 'Bob'
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
import math
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    if n % 2 == 1:
        print('Bob')
    elif math.log2(n) == int(math.log2(n)):
        if int(math.log2(n)) % 2 == 1:
            print('Bob')
        else:
            print('Alice')
    else:
        print('Alice')