ACM SGU/volume 1/106

106. The equationПравить

УсловиеПравить

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


ОграниченияПравить

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


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

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

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


 


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

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