RANGEGAME - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: muhammadhassan
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Nim, the Sprague-Grundy theorem

PROBLEM:

You’re given L, R, and a prime P.
Consider an array A of length R-L+1, where A_i = L+i-1.
That is, A = [L, L+1, L+2, \ldots, R].
Two players play the following game:

  • Choose an index i and an integer k\gt 0 such that P^k divides A_i.
  • Divide A_i by P^k.

The player who cannot make a move loses.
With optimal play, who wins?

EXPLANATION:

Let’s restate the game a bit, to bring it to a more familiar form.

Define B_i to be the largest integer such that P^{B_i} divides A_i.
For example, if P = 3, then:

  • If A_i = 18 then B_i = 2 since 3^2 = 9 divides A_i but 3^3 doesn’t.
  • If A_i = 2 then B_i = 0 since 3^0 = 1 divides A_i but 3^1 doesn’t.

With this array B, our operation of dividing A_i by P^k turns into subtracting k from B_i.
We’re now in familiar territory: we have an array from which on each turn, a player must subtract a positive number from some index; whoever can’t make a move loses.
This is exactly the classical nim game!

The solution to this game is well-known.
Let X = B_1\oplus B_2\oplus\ldots B_{R-L+1} be the xor-sum of all the elements.
Then, the first player wins if X\gt 0, and the second player wins if X = 0.

Now we know how to solve the problem, but our solution is too slow since R can be quite large - we definitely can’t actually create the entire array B and then compute its xor-sum.

To optimize, observe that B_i \leq 60 for any i, because 2^{60} \gt 10^{18} (and so P^{60}\gt 10^{18} for any prime P).
So, let’s fix the value of B_i to k (1 \leq k \leq 60), and try to count the number of times it occurs in the array B.

For a fixed k, we’d like to know the number of integers in the range [L, R] whose highest power of P is exactly P^k.
In particular, any such integer must be a multiple of P^k.
The number of multiples of P^k in this range is exactly

\left\lfloor \frac{R}{P^k} \right\rfloor - \left\lfloor \frac{L-1}{P^k} \right\rfloor

Of them, we need to remove anything that has a higher power of P dividing it; which is just all the multiples of P^{k+1} in this range!
So, the count we’re looking for is nothing but

\left(\left\lfloor \frac{R}{P^k} \right\rfloor - \left\lfloor \frac{L-1}{P^k} \right\rfloor\right) - \left(\left\lfloor \frac{R}{P^{k+1}} \right\rfloor - \left\lfloor \frac{L-1}{P^{k+1}} \right\rfloor\right)

Observe that:

  • If the count is even, the overall contribution of B_i = k to the xor-sum is 0; because x\oplus x = 0.
  • If the count is odd, the overall contribution of B_i = k to the xor-sum is k.
    This is because an even number of occurrences will cancel out, leaving only a single k remaining.

So, our final solution is as follows:

  • Let X denote the xor-sum of array B.
    Initially, X = 0.
  • For each k, find the number of times B_i = k occurs.
  • If this count is odd, update X as X := X\oplus k

Finally, if X = 0 the second player wins, otherwise the first player wins.

TIME COMPLEXITY:

\mathcal{O}(\log_P R) per testcase.

CODE:

Tester's code (C++) 
for _ in range(int(input())):
    l, r, p = map(int, input().split())
    x = 0
    cur, pw = p, 1
    while cur <= r:
        ct = r//cur - (l-1)//cur - (r//(cur * p) - ((l-1)//(cur * p)))
        if ct & 1: x ^= pw
        cur *= p
        pw += 1
    print('Second' if x == 0 else 'First')
Editorialist's code (Python) 
for _ in range(int(input())):
    l, r, p = map(int, input().split())
    x = 0
    cur, pw = p, 1
    while cur <= r:
        ct = r//cur - (l-1)//cur - (r//(cur * p) - ((l-1)//(cur * p)))
        if ct & 1: x ^= pw
        cur *= p
        pw += 1
    print('Second' if x == 0 else 'First')
1 Like
2

The magical “nimbers” :slight_smile: