Навеяно 163B - Лемминги.

Предположим, загадано рациональное число, представленное в виде несократимой дроби 0 ≤ p / q ≤ 1. Пусть знаменатель не превосходит Q (в задаче, да и обычно на практике — 10⁹). Есть способ по данному рациональному числу узнавать, больше оно данного, меньше или равно (функция f (p, q) → {1, 0,  - 1}). Задача: с помощью вызовов этой функции отгадать загаданное число. При этом функции нельзя передавать числа со знаменателем  > Q. Вещественной арифметикой пользоваться нельзя. За какую асимптотику от максимального значения знаменателя (от точности, по сути) можно решить эту задачу? Простому бинпоиску, как мне кажется, этой информации недостаточно — он оперирует значением числа, а не его представлением.

Первое приходящее в голову решение: перебираем знаменатель, потом ищем числитель бинарным поиском. Сложность — O(Q·logQ), что плохо.

Второе решение с использованием ряда Фарея, уже за O(Q), по схеме бинарного поиска. Поддерживаем отрезок, в котором может находиться число, с границами p_l / q_l и p_r / q_r, изначально равными 0 и 1 соответственно. На каждом шаге находим p_m / q_m, где p_m = p_r + p_l, q_m = q_r + q_l, скармливаем это число функции и в зависимости от этого переходим в правую или левую часть отрезка. Из ряда Фарея следует, что мы за не более чем q шагов найдем требуемую дробь. Получили O(Q). Но хочется логарифм или хотя бы что-то сублинейное.

Мне кажется, что я сейчас изобретаю велосипед и что-то такое давным-давно делать умеют. Как можно решать такую задачу?