扩展欧几里得

内容

给定 \(a, b\)，求出 \(ax+by=\gcd(a, b)\) 的一组 \(x, y\)。

int exgcd(int a, int b, int &x, int &y){
  if(a == 0){
    x = 0, y = 1; return b;
  } else {
    int x0 = 0, y0 = 0;
    int d = exgcd(b % a, a, x0, y0);
    x = y0 - (b / a) * x0, y = x0;
    return d;
  }
}