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