Для начала рассмотрим отдельно случаи, когда или . Сделать это несложно.
Теперь найдём любую пару , что . Здесь — Наибольший Общий Делитель двух чисел. Найти такую пару можно с помощью Алгоритма Евклида за . Несложно доказать, что все решения теперь будут иметь вид:
Отсюда следует, что если , то решений нет.
Теперь с помощью бинарного поиска (так как функции вида «точка левее/правее точки » являются монотонными) мы можем найти такие коэффициенты , что точки и являются крайними точками решения.
Очевидно, что тогда ответом задачи будет число .
