https://codeforces.me/problemsets/acmsguru/problem/99999/106 can someone please help me solve this?
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
https://codeforces.me/problemsets/acmsguru/problem/99999/106 can someone please help me solve this?
| Name |
|---|



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..
how to find the bounds?
If $$$b \gt 0$$$, you have
If b < 0, the inequalities are reversed.
You similarly get another relation from the other inequality.
Take note of the fact that what I have written above is real division, not integer division.
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.