Two Piles, Diagonal Moves — Solution & Editorial

Back to the Problem

Wythoff's game: the losing (P) positions are (⌊kφ⌋, ⌊kφ²⌋) for k ≥ 0, where φ is the golden ratio. With a = min, b = max and k = b−a, the position loses iff a = ⌊kφ⌋.

Complexity: O(1)

Watch out: Floating φ near 10⁹ can be off by one — the intended solution rounds carefully (integer Beatty-sequence test).