XOR and Primes

Codeforces 931 D2 XOR Break - Game Version: This problem defines a way of decomposing a positive integer: for a given positive integer p, if there exist 0 < p1, p2 < p such that p1 xor p2 == p, then this is called an XOR decomposition of p. The problem provides a positive integer n, and asks whether Alice has a winning strategy by continuously performing XOR decomposition on the number, with the player unable to further decompose a number losing the game. The original problem statement can be found on the Codeforces 931 D2 XOR Break page.

This XOR decomposition may seem unfamiliar at first, but upon closer observation, it closely resembles the (prime factor) multiplication decomposition of positive integers: for a positive integer p, we can consider whether there exist p1, p2 < p such that p1 x p2 == p. When is decomposition impossible? This happens precisely when p is a prime number, that is, p cannot be decomposed if and only if it is a prime number. Returning to the previous problem, what are the "prime numbers" under XOR decomposition? If p has only one set bit, meaning p is a power of 2, then decomposition is impossible; otherwise, as long as p has at least two set bits, it can always be decomposed. So, powers of 2 are the "prime numbers" under XOR decomposition.

Now, let's consider the winning strategy. What kind of number ensures victory in the game? Let's use multiplication decomposition as an analogy again. If the number is a prime number, then the game is lost. If the number can be written as the product of two prime numbers, that is, p == p1 x p2, then the game is won. This is because in this case, the opponent cannot further decompose either p1 or p2. It can be proven by mathematical induction that as long as the number obtained has an even number of prime factors, victory is assured; otherwise, it is a loss. Returning to the original problem, victory is assured if the obtained number has an even number of set bits; otherwise, it is a loss.

Since the original problem specifies that Alice can choose to act first or second, Alice has a winning strategy. Specifically:

• If n has an even number of set bits, Alice chooses to go first. She can decompose n into two numbers with an odd number of set bits each (the essence here is that an even number can be written as a sum of two odds). This way, Bob can only obtain numbers with an odd number of set bits, and Alice wins the game.
• Otherwise, Alice chooses to go second. Since n has an odd number of set bits, Bob can only decompose it into one number with an odd number of set bits and one number with an even number of set bits (the essence here is that an odd number can only be written as a sum of an odd and an even). Thus, Alice can choose the number with an even number of set bits, and she wins the game.

Here, we have found a new definition of "prime numbers," which can be referenced back and forth with the commonly defined prime numbers to help us solve problems.

back