Потеря медальона

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

Для начала заметим, что не более чем за $$$x - 1$$$ запрос мы можем узнать остаток при делении на $$$x$$$ текущей координаты медальона с помощью следующего алгоритма:

  1. сделаем запрос числом $$$x$$$;
  2. если получим ответ $$$1$$$ — значит координата делится на $$$x$$$, то есть имеет остаток 0 при делении на $$$x$$$;
  3. если получим ответ $$$0$$$, то продолжим алгоритм, пока не встретим число $$$1$$$.

Тогда, если мы потратили $$$y$$$ действий, значит $$$y - 1$$$ раз мы получили ответ $$$0$$$, на $$$y$$$-й запрос получили ответ 1. Тогда понятно, что изначальная константа имеет остаток $$$y - 1$$$ при делении на $$$x$$$. Также заметим, что последний ($$$x$$$-й) запрос можно не делать, если мы до него дошли, ведь в таком случае мы гарантировано получим ответ $$$1$$$. Тогда, не более чем за $$$x - 1$$$ запрос можно получить остаток при делении на $$$x$$$ начального числа.

Важно отметить, что также можно находить остатки при делении на несколько чисел — после нахождения остатка начального числа (назовем его $$$s$$$) при делении на $$$x_1$$$ (назовем остаток $$$p_1$$$) можно запомнить, сколько мы вычли из изначального числа, и после этого найти остаток при делении на $$$x_2$$$ числа $$$s - p_1$$$, тогда $$$s - p_1 \equiv p_2 \pmod{x_2}$$$, значит $$$s \equiv p_1 + p_2 \pmod{x_2}$$$.

Тогда, с помощью описанного выше алгоритма найдем остатки при делении начальной координаты $$$s$$$ на первые семь простых чисел: $$$2$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$11$$$, $$$13$$$, $$$17$$$. После будем иметь систему: $$$\forall 1 \leq i \leq 7,\ s \equiv r_i \pmod{p_i}$$$. Всего на это мы потратим $$$\sum\limits_{i=1}^{7} (p_i - 1) = 1 + 2 + 4 + 6 + 10 + 12 + 16 = 51$$$ запрос.

В конце воспользуемся Китайской теоремой об остатках, которая говорит о единственности такого $$$x$$$, что $$$0 \leq x < \prod\limits_{i=1}^{n} m_i$$$ и $$$\forall 1 \leq i \leq n$$$ можно записать $$$x \equiv r_i \pmod{m_i}$$$, при условии взаимной простоты $$$m_i$$$. В нашем случае модули очевидно взаимно просты (это различные простые), тогда в границах от $$$0$$$ до $$$\prod\limits_{i=1}^7 p_i = 510510$$$ существует единственное число $$$s$$$, подходящее заданным условиям.

Для поиска этого ответа воспользуемся алгоритмом Гарнера для решения системы в условиях КТО, или даже просто переберем все возможные числа от $$$0$$$ до $$$5 \cdot 10^5$$$ и проверим совпадение остатков. Даже решение без алгоритма Гарнера укладывается в ограничения по времени, так как сумма ответов по всем тестовым случаям не превосходит $$$5 \cdot 10^5$$$.