Solução escrita por João Pedro
Conhecimento prévio necessário:
- Operações binárias em números
Chame de $$n(x)$$ a quantidade de bits ativos na representação binária de $$x$$. Agora, perceba que se $$a \oplus b = c$$, $$n(a) + n(b) \equiv n(c)~(mod~2)$$. Já que para cada bit ativo em $$c$$ temos somente 1 bit ativo no total, e para cada bit desativado temos ou 2 ou 0 bits ativos no total. Logo, como é $$(mod~2)$$ podemos desconsiderar os bits desativados de $$c$$, já que somam 2 ou 0 pra $$n(a) + n(b)$$. Como temos exatamente $$n(c)$$ bits ativos, chegamos a conclusão que $$n(a) + n(b) \equiv n(c)~(mod~2)$$.
Também perceba que o único caso onde o jogo está perdido para o jogador que vai escolher entre $$p_1$$ e $$p_2$$ para quebrar é quando $$n(p_1) = n(p_2) = 1$$. Já que é impossível dividir um número $$p$$ de 1 bit ativo em $$p_1$$ e $$p_2$$ seguindo as condições que $$p_1 \oplus p_2 = p$$ e $$0 < p1, p2 < p$$. Perceba que para chegar em $$n(p_1) = n(p_2) = 1$$ só podemos ter quebrado um número que tem $$n(p) \equiv 0~(mod~2)$$, por conta da observação anterior. Logo, chegamos a conclusão que o único estado ganhador advém de quebrar um número que tem $$n(p)$$ par.
Também perceba que sempre podemos garantir que sempre cairemos em um estado par, enquanto nosso oponente caí em um estado ímpar. Já que podemos quebrar um $$p$$ com $$n(p)$$ par em dois $$p_1$$ e $$p_2$$ com $$n(p_1)$$ e $$n(p_2)$$ ímpar, fazendo com que o oponente só possa escolher um número $$x$$ com $$n(x)$$ ímpar. E um oponente que vai quebrar um $$n(p)$$ ímpar só pode dividir ele em um ímpar e em um par, e quando isso acontece podemos simplesmente escolher o par toda vez. Como vamos diminuir o MSB (Most Significant Bit) do número em pelo menos 1 toda rodada, temos certeza que o jogo não dura mais que $$log2(10^{18}) < 63$$, logo não precisamos nos preocupar com o limite.
Concluindo, nossa estratégia é:
- Se o número inicial $$n$$ for par, jogar primeiro, se não, jogar segundo.
- Sempre que tiver a opção de escolher entre $$p_1$$ e $$p_2$$ escolha o que tem $$n(x)$$ par (como nosso oponente sempre caí em um ímpar garantimos que sempre vai ter essa opção).
- Quando for quebrar um número com $$n(p)$$ par, quebre ele em dois $$p1, p2$$ tal que $$n(p_1) \equiv n(p_2) \equiv 1~(mod~2)$$.
Assim, garantimos que nunca perdemos o jogo!
Clique aqui para ver o código.