## Editorial for DMOPC '22 Contest 4 P5 - Blackboard Game

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: mangoqwq

Consider the sum of where are the numbers currently written on the board. This sum decreases by exactly on each move. Thus, we can find the winner by considering the parity of this sum.

The described game is an impartial game, and the remainder of the editorial will assume knowledge of the Sprague-Grundy theorem.

Observe that we only need to care about the prime factorizations of the numbers on the board. More specifically, for , we only care about the multiset .

It turns out there are around such multisets for blackboard numbers between and . To reduce the number of states, observe that multisets and (adding one to ) will always have the same Grundy number. This can be proved inductively, but the intuition is that if prime factor of has multiplicity , we cannot do anything with when splitting into and .

With this observation, the number of states is cut down to around . Then we can compute Grundy values in , where is the number of such states. Since we do not care for prime factors of multiplicity , we can calculate the multisets corresponding to each in time. Hence we have solved this problem in .

Note from the problem author: Thanks to mangoqwq for preparing the problem :)