Просмотр кода страницы ACM SGU/volume 1/106

=106. The equation=

== Условие ==

Необходимо найти количество целых решений уранения <math> a \cdot x + b \cdot y + c = 0 \!</math>  таких, что <math> x_1 \le x \le x_2 \!</math>  и  <math> y_1 \le y \le y_2 \!</math>.


== Ограничения ==

<math>- 10^8 \le a, b, c, x_1, x_2, y_1, y_2 \le 10^8\!</math>
Все числа целые.


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

Для начала рассмотрим отдельно случаи, когда <math>a = 0\!</math> или <math>b = 0\!</math>. Сделать это несложно.

Теперь найдём любую пару <math>(x_0; y_0)\!</math>, что <math> a \cdot x_0 + b \cdot y_0 = GCD (a, b) \!</math>. Здесь <math>GCD (a, b)\!</math> — Наибольший Общий Делитель двух чисел. Найти такую пару можно с помощью [[w:Алгоритм Евклида|Алгоритма Евклида]] за <math>O(log N)\!</math>. Несложно доказать, что все решения теперь будут иметь вид:


<math>\left\{\begin{matrix} x = x_0 \cdot (- c / GCD (a, b)) + k \cdot b / GCD (a, b) \\ y = y_0 \cdot (- c / GCD (a, b)) - k \cdot a / GCD (a, b) \end{matrix}\right. \!</math>


Отсюда следует, что если <math>c\mod GCD(a, b) \neq 0\!</math>, то решений нет.

Теперь с помощью бинарного поиска (так как функции вида «точка <math>(x_1, y_1)\!</math> левее/правее точки <math>(x_2, y_2)\!</math>» являются монотонными) мы можем найти такие коэффициенты <math>k_1, k_2\!</math>, что точки <math>(x_{k_1}, y_{k_1})\!</math> и <math>(x_{k_2}, y_{k_2})\!</math> являются крайними точками решения.
Очевидно, что тогда ответом задачи будет число <math>|k_1 - k_2| + 1\!</math>.
[[Категория:ACM SGU|volume 1/106]]