The equation
A Linear Diophantine Equation is an equation of the general form:
$$$\underset{i = 1}{\overset{n}{\Sigma}} (a_i \cdot x_i) = N$$$
Where $$$a_i$$$ and $$$N$$$ are given integers and $$$x_i$$$ are unknown integers.
The problem
Given Linear Diophantine Equation of only 2 variables:
$$$ax + by = c$$$
With given integers $$$a, b, c$$$ and unknown integers $$$x, y$$$
Some interesting property
We have to count the number of $$$(x, y)$$$ non-negative integers solutions for the equation (assume that these value are under $$$10^9$$$ so that we dont deal with overflow cases$
Can I have a simplier implementation then this ? (My algorithm based on cp-algorithm)
Recursive extended greatest common divisor
Recursive extended greatest common divisor
Find one solution ax + by = c
Shift solution
Count number solutions of ax + by = c with given range x & range y
Count all nonegative solutions (x, y) satisfy ax + by = c