106. The equation

править

Условие

править

Необходимо найти количество целых решений уранения   таких, что   и  .


Ограничения

править

  Все числа целые.


Решение с помощью бинарного поиска

править

Для начала рассмотрим отдельно случаи, когда   или  . Сделать это несложно.

Теперь найдём любую пару  , что  . Здесь   — Наибольший Общий Делитель двух чисел. Найти такую пару можно с помощью Алгоритма Евклида за  . Несложно доказать, что все решения теперь будут иметь вид:


 


Отсюда следует, что если  , то решений нет.

Теперь с помощью бинарного поиска (так как функции вида «точка   левее/правее точки  » являются монотонными) мы можем найти такие коэффициенты  , что точки   и   являются крайними точками решения. Очевидно, что тогда ответом задачи будет число  .