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?