Блог пользователя om1429888

Автор om1429888, история, 4 года назад, По-английски
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

Note that if $$$\gcd(a, b) \not\mid c$$$, no solution exists. Otherwise, divide $$$a, b, c$$$ by this $$$\gcd$$$, now we assume $$$\gcd(a, b) = 1$$$.

Let $$$x_0, y_0$$$ be any integer solution of the equation (which can be found using Euclid's algorithm).

One can prove that all solutions of the equation must be of the form $$$(x_0 - b n, y_0 + a n)$$$ for some integer $$$n$$$.

Now, we end up with the problem of counting integer $$$n$$$ such that $$$x_1 \le x_0 - b n \le x_2$$$, $$$y_1 \le y_0 + a n \le y_2$$$.

This can be done by just getting min and max bounds on $$$n$$$ using the above inequalities. Make sure to take care of all the cases such as $$$a = 0$$$, $$$a \lt 0$$$, when the upper bound is less than the lower bound, etc..

»
4 года назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

You can take reference from CP-algorithms's tutorial on Linear Diophantine Equations. They have the exact solution. There are a lot of edge cases to consider like if a == 0 or b == 0 etc, or a < 0 or b < 0.

Python Solution. Note that '//' is a floor divide in Python