Простая игра

Автор задачи и разработчик: Павел Скобелин

В игре выигрывает тот, после чьего хода сумма чисел становится простым числом. Давайте обозначим: $$$s = A + B$$$. Тогда, если мы уменьшаем/увеличиваем числа $$$A$$$/$$$B$$$ на какие-то значения, то $$$s$$$ изменится на такое же значение. Обозначим за $$$l$$$ наибольшее простое число, меньшее $$$s$$$, а за $$$r$$$ — наименьшее простое число, большее $$$s$$$. Заметим, что в пределах игры (кроме, может быть, последнего хода) сумма текущих $$$A$$$ и $$$B$$$ будет лежать в пределах от $$$l$$$ до $$$r$$$. Действительно, если в какой-то момент игрок «перепрыгнул» $$$l$$$ или $$$r$$$, то он мог этим ходом выиграть.

Как найти $$$l$$$ и $$$r$$$? Очень просто, для этого нужно понять факт, что $$$l$$$ и $$$r$$$ — соседние простые числа, а расстояние между соседними простыми числами до $$$10^9$$$ не превосходит $$$300$$$ (эмпирическое наблюдение). Тогда можно найти эти границы наивно, проверяя числа на простоту проверкой делителей до корня. Эта часть будет работать за $$$\mathcal{O}(\sqrt{A + B} \cdot 300)$$$.

В начале стоит проверить, что Зельда сможет выиграть за один ход. В каком случае она может это сделать? Она может или прибавить что-то к числу $$$B$$$, в таком случае должно выполняться неравенство $$$s + k \geq r$$$. Также она может вычесть что-то из числа $$$A$$$, в таком случае должно выполняться $$$s - k \leq l$$$, но в этом случае нужно не забыть про то, что $$$A$$$ должно оставаться натуральным: то есть $$$A - (s - l) \geq 1$$$.

Если Зельда не может выиграть за один ход, подумаем про выигрышные и проигрышные позиции. Выигрышной суммой назовем такую, что, начиная с такой суммы, игрок может выиграть, проигрышной суммой — не выигрышную. В таком случае можем считать $$$r$$$ проигрышной суммой. Тогда все суммы в промежутке $$$[r - k, r)$$$ — выигрышные. Но тогда сумма $$$r - (k + 1)$$$ — проигрышная. Рассуждая так далее, несложно понять, что проигрышными суммами являются только суммы вида $$$r - (k + 1) \cdot z, z \in \mathbb{N}$$$ (удобно представить в виде таблицы, в которой помечать выигрышные и проигрышные позиции). Тогда, если $$$(r - s) \bmod (k + 1) = 0$$$, то Зельда не сможет выиграть, иначе сможет.

Итого получаем решение за $$$\mathcal{O}(\sqrt{A + B} \cdot 300)$$$ на один набор входных данных.