Number of non-negative solutions of the equation ax + by = c

Revision en1, by BumbleBee, 2018-10-22 20:03:19

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?

Tags diofant equation, diophantine, gcd, extended euclid


  Rev. Lang. By When Δ Comment
en1 English BumbleBee 2018-10-22 20:03:19 562 Initial revision (published)