Free Mango

Prerequisite: Nim Game (Game Theory), Divisor Sieve (Number Theory)

Explanation: At first, we have to calculate the number of mangoes in each tree in an efficient way. For this, we can precalculate the number of divisors $1$ to $10^6$using the divisor sieve.

for (int i = 1; i <= 1000000; i++)
    for (int j = i; j <= 1000000; j += i)
        d[j]++; // divisor count

Now, we can think of each mango tree as a single NIM pile as the game can be considered as a classical NIM game. From NIM game we know that the current player has a winning strategy if and only if the xor-sum of the pile sizes is non-zero. So, we have to calculate the xor-sum of all $D(i)$ from $L$ to $R$. But we have to answer a lot of queries so we can not iterate the range for every query. Here, we can use a characteristic of XOR to answer all queries in $O(1)$. We will calculate the cumulative xor-sum of all $D(i)$ from $1$ to $10^6$.

for (int i = 1; i <= 1000000; i++)
        cxor[i] = cxor[i - 1] ^ d[i];

According to XOR’s characteristic, $d[L]\oplus d[L+1]\oplus … \oplus d[R] = cxor[R]\oplus cxor[L-1]$. Now we can answer each query in $O(1)$.

Time Complexity: Precalculation of divisor sieve in $O(N log N)$ and Calculation of cumulative xor-sum in $O(n)$ and answering each query in $O(1)$.

Solution:

Setter’s Solution