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

You had to solve a linear diophantine equation:

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

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

And all solutions can be written as

The problem is, that this can easily give an integer overflow. E.g. when a, b and c are as large as 10¹⁸. To solve the problem 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 want a solution for a·x + b·y = c with |a|, |b| ≤ 10¹⁸.

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);