Linear Diophantine Equations

If you want to understand everything, read this [cp-algorithms] - Linear Diophantine Equations. I think this code is much better. It's possible to do it iteratively, but that's probably unnecessary.

Extended GCD

Given two integers \(a\) and \(b\), returns their gcd and two coefficients \(x\) and \(y\) such that \(ax + by = g\).

Linear Diophantine Equations

Given three integers \(a\), \(b\), \(c\), returns whether it is possible to get \(x\) and \(y\) such that \(ax + by = c\), as well as \(x\) and \(y\) if possible.

Extended GCD

// Extended GCD {{{
tuple<int, int, int> ext_gcd(int a, int b) {
  if (b == 0) return {a, 1, 0};
  auto [g, x, y] = ext_gcd(b, a%b);
  return {g, y, x - (a/b) * y};
}

tuple<bool, int, int> dio(int a, int b, int c) {
  auto [g, x, y] = ext_gcd(a, b);
  if (c % g) return {false, -1, -1};
  return {true, x * (c/g), y * (c/g)};
}
//}}}