Solutia problemei Cmmdcgame

Cunostinte necesare: teorema Sprague-Grundy, nimber-uri. Autorul problemei recomanda acest tutorial

Conform teoremei Sprague-Grundy, jocul din enunt se poate reduce la un joc de nim pe o singura gramada (nimber-ul jocului). Cum adunarea pe nimber-uri corespunde operatiei XOR, si suma a doua jocuri, in acest sens, este jocul ce rezulta prin jocul in paralel a celor doua jocuri, se poate arata ca este suficient sa calculam nimber-ul fiecarei gramezi (oras, in enunt), apoi sa calculam XOR-ul lor, si apoi sa vedem daca rezultatul este 0 (in care caz castiga al doilea jucator) sau nu (in care caz castiga primul jucator).

Care este nimber-ul unei gramezi (oras)? Stim ca nimber-ul unei stari dintr-un joc este egal cu cel mai mic nimber la care nu putem ajunge printr-o mutare din acea stare. Mai intai sa ne gandim la nimber-ul unei gramezi de marime prima (sau 1). Din aceasta stare putem sa mergem in oricare marime mai mica de gramada -- inclusiv toate marimile prime (sau 1) mai mici. Asta implica ca numerele prime (si 1) au nimber-uri strict crescatoare. Ba chiar, daca jocul ar permite sa mergem doar prin gramezi de marime prima (sau 1), atunci 1 ar avea nimber-ul 0, 2 nimber-ul 1, 3 nimber-ul 2, 5 nimber-ul 3, 7 nimber-ul 4 si asa mai departe. Sa presupunem pe moment ca aceste atribuiri de nimber-uri sunt corecte. Care ar fi atunci nimber-ul unui numar compus? Este clar ca dintr-un numar compus putem muta in toate numerele prime (si 1) mai mici ca cel mai mic factor prim al numarului nostru. Totodata nu putem muta in niciun numar care impartaseste acest factor prim minim (ca acel numar ar fi necoprim cu numarul actual). Asta ne arata ca nimber-ul unui numar compus este egal cu nimber-ul celui mai mic factor prim al numarului (acest fapt se poate demonstra riguros prin inductie).

Astfel, concret, pentru a rezolva problema, calculam, cu ajutorul unui ciur (analog cu ciurul lui Eratostene), pentru fiecare marime posibila de oras, valoarea f(x), egala cu cel mai mic factor prim al lui x, respectiv i(x), egala cu indicele lui x ca numar prim (sau 1), adica i(1) = 0, i(2) = 1, i(3) = 2, i(5) = 3, i(7) = 4, etc. Atunci, calculam XOR-ul valorilor i(f(x)) pentru toate marimile x de orase, si afisam ca primul jucator (adica Daenarys) castiga daca si numai daca aceasta valoare este nenula.