Запит повертає першу цифру числа n \cdot x, а перша цифра — це, по суті, інформація про дробову частину десяткового логарифма. Справді, перша цифра числа дорівнює тоді й лише тоді, коли
де позначає дробову частину.
Позначимо t = \{\log_{10} n\} — саме цю величину ми й шукатимемо. Оскільки \log_{10}(nx) = \log_{10} n + \log_{10} x, кожен запит повідомляє, у який із дев'яти проміжків потрапляє \{t + \log_{10} x\}.
Це дозволяє робити двійковий пошук по . Підтримуємо відрізок [lo, hi), у якому лежить , і беремо його середину . Тепер підберемо так, щоб межа між відповіддю «» і відповіддю «» припала рівно на , тобто щоб
Для цього візьмемо — найближче ціле до 10^{\,\log_{10} 2 - \mathit{mid} + k}, де показник підібраний так, щоб було якнайбільшим у межах 10^9 (що зменшує похибку округлення).
Тоді відповідь d = 1 означає t < \mathit{mid}, а d \ge 2 — що t \ge \mathit{mid}; звужуємо відрізок і повторюємо. Кожен запит дає рівно один біт.
Скільки бітів треба? Сусідні цілі і n+1 при n < 10^8 відрізняються за логарифмом приблизно на \frac{1}{n \ln 10} \approx 4 \cdot 10^{-9}, тому щоб їх розрізнити, потрібно близько \log_2 (1/4\cdot 10^{-9}) \approx 28 бітів. Саме тому ліміт — запитів, і кожен із них має давати повноцінний біт; «марнувати» запити не можна.
Відновлення . Знаючи з достатньою точністю, ми знаємо мантису числа. Залишилось визначити порядок — і тут стає в пригоді умова, що не ділиться на : числа , , мають однакову дробову частину логарифма, тож без цієї умови задача була б нерозв'язною. Отже, серед кандидатів \mathrm{round}(10^{\,t + j}) для різних рівно один не кратний десяти — він і є відповіддю.
Не забувайте про flush після кожного запиту й рахуйте логарифми в типі long double, щоб не втратити потрібні дев'ять значущих цифр.