На самом деле достаточно сделать $20$ запросов. Стоит вспомнить, что любое число представимо в двоичной записи. Нам известно, что младший (нулевой) бит числа равен $1$ ($p$ простое и $p \ge 3$). Попробуем угадать первый бит. Спросим, правда ли остаток от деления на $4$ равен $1$. При положительном ответе первый бит равен $0$, при отрицательном~--- $1$. Аналогично будем угадывать остальные биты по возрастанию, в качестве $d$ будем использовать уже построенное число. Поскольку $p \le 10^6 < 2^{20}$, за девятнадцать запросов мы спросим биты, соответствующие $2^1, 2^2, \ldots, 2^{19}$, а значит полностью восстановим число. Двадцатым запросом выведем ответ.
