ACM SGU/volume 1/106

Материал из Викиучебника — открытых книг для открытого мира
< ACM SGU‎ | volume 1(перенаправлено с «ACM SGU 106»)
Перейти к навигации Перейти к поиску

106. The equation[править]

Условие[править]

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


Ограничения[править]

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


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

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

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



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

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