Problem Solving IV Note 07

Chapter 31: 数论算法

int exgcd (int a, int b, int &x, int &y) {
  if (!b) {
      x = 1, y = 0;
      return a;
  }
  int ans = exgcd (b, a % b, y, x);
  y -= a / b * x;
  return ans;
}