Avoid overflow in linear diophantine equation:

Revision en2, by Jakube, 2018-06-04 15:46:04

I solved 986F - Oppa Funcan Style Remastered today and faced the following problem.

You had to solve a linear diophantine equation:

a·x + b·y = c

This is of course quite easy, with the extended Euclidean algorithm you can find a solution:

a·x0 + b·y0 = g

and by multiplying with c / g gives a final solution:

a·(x0·c / g) + b·(y0·c / g) = c

And all solutions can be written as

a·(x0·c / g + k·b / g) + b·(y0·c / g - k·a / g) = c

The problem is, that this can easily give an integer overflow. E.g. when a, b and c are as large as 1018. In my solution I just took my BigInteger implementation. But this is of course quite ugly (400 additional lines of code just for one simple calculation).

How can we avoid the overflow?

I found the following code in the solution of tourist. But I'm unable to wrap my head around it. Can somebody explain me the logic of this formula?

g = extgcd(a, b, x, y);
if (c % g != 0) {
  return false;
}
long long dx = c / a;
c -= dx * a;
long long dy = c / b;
c -= dy * b;
x = dx + mulmod(x, c / g, b);
y = dy + mulmod(y, c / g, a);
g = abs(g);

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Jakube 2018-06-04 15:50:08 4 Tiny change: 'c$ with $|a|, |b| \le 10^1' -> 'c$ with $|x|, |y| \le 10^1' (published)
en4 English Jakube 2018-06-04 15:49:05 77
en3 English Jakube 2018-06-04 15:47:34 22 Tiny change: '0^{18}$.\nIn my solution I just to' -> '0^{18}$.\nTo solve the problem I just to'
en2 English Jakube 2018-06-04 15:46:04 2 Tiny change: 'ing with $$c / g$$ gives a ' -> 'ing with $c / g$ gives a '
en1 English Jakube 2018-06-04 15:45:19 1289 Initial revision (saved to drafts)