https://codeforces.me/problemsets/acmsguru/problem/99999/106 can someone please help me solve this?
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 7 | nik_exists | 133 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
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.