106. The equation

Условие

Необходимо найти количество целых решений уранения $a\cdot x+b\cdot y+c=0\!$ таких, что $x_{1}\leq x\leq x_{2}\!$ и $y_{1}\leq y\leq y_{2}\!$ .

Ограничения

$-10^{8}\leq a,b,c,x_{1},x_{2},y_{1},y_{2}\leq 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)\!$ . Несложно доказать, что все решения теперь будут иметь вид:

$\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.\!$

Отсюда следует, что если $c\mod GCD(a,b)\neq 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\!$ .