Linear Diophantine Equation

Revision en3, by SPyofgame, 2020-11-24 17:02:25

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
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
Tags linear diophantine, c++, math, extended gcd

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English SPyofgame 2020-11-24 17:16:55 55
en4 English SPyofgame 2020-11-24 17:06:42 361
en3 English SPyofgame 2020-11-24 17:02:25 558 Tiny change: 'rset{n}{\Sigma}} a_i \cd' -> 'rset{n}{\SIGMA}} a_i \cd'
en2 English SPyofgame 2020-11-24 16:52:29 393
en1 English SPyofgame 2020-11-24 16:48:03 4234 Initial revision (published)