I want to count the number of non-negative solutions of the equation: ax + by = c.
I know the naive approach where I can iterate over all non-negative y such that c - by is non-negative and count if c - by is divisible by a. Before starting iteration, I can check if c is a multiple of the greatest common divisor of a and b. If not, then I can simply return zero. But this will cost huge runtime for large values of a, b and c.
What is the most efficient solution for this?
a * x + b * y = c. Firstly notice that if c is not divisible by GCD(a, b) then the equation has no roots. Otherwise you can divide the both sides by GCD(a, b). Now you can run the Extended Euclid Algorithm. It will give you some integers x1 and y1, for which is hold, that a * x1 + b * y1 = GCD(a, b). Notice that the GCD of (a, b) is now 1, since we divided the both sides with the GCD of the initial (a, b). So if we multiply x1 and y1 with the GCD of the initial (a, b), then a * x1 + b * y1 = c. And now it is known that all other roots are obtained, by the formula: x = x1 — b * i, y = y1 + a * i, where i is an integer. You can simply prove that this is correct, since a * (x1 — b * i) + b * (y1 + a * i) = a * x1 — a * b * i + b * y1 + a * b * i = a * x1 + b * y1 = c. So to find the number of the all non-negative solutions, you just need to find the number of the i-s, for which is hold x1 — b * i >= 0 and y1 + a * i >= 0. So x1 >= b * i and y1 >= — a * i. And we receive the following: i <= x1 / b and i >= — y1 / a. So now you have to find the number of the roots of this system inequations, which is easy.
Same Problem