ACM SGU/volume 1/106

106. The equation

Условие

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

Ограничения

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

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

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

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

$\{\begin{array}{c}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{array}$

Отсюда следует, что если $cmodGCD(a,b)\ne 0$, то решений нет.

Теперь с помощью бинарного поиска (так как функции вида «точка $(x_1,y_1)$ левее/правее точки $(x_2,y_2)$» являются монотонными) мы можем найти такие коэффициенты $k_1,k_2$, что точки $(x_{k_1},y_{k_1})$ и $(x_{k_2},y_{k_2})$ являются крайними точками решения. Очевидно, что тогда ответом задачи будет число $|k_1-k_2|+1$.