拓展欧几里得

欧几里得算法：$gcd(a,b)=gcd(b,a$ $mod$ $b)$

证明

扩展欧几里得算法$:(ExtendedEuclideanalgorithm,EXGCD)$

常用于求 $$ ax+by=gcd (a, b) $$ 的一组可行解。

$a{x}_1+b{y}_1=a{y}_2+b{x}_2-\lfloor \frac{a}{b}\rfloor \times b{y}_2=a{y}_2+b(x_2-\lfloor \frac{a}{b}\rfloor y_2)$

$a=a,b=b$ ,$\Rightarrow$ $x_1=y_2,y_1=x_2-\lfloor \frac{a}{b}\rfloor y_2$

将 $x_2,y_2$ 不断代入递归求解直至 $gcd$$($ 最大公约数，下同 $)$ 为 $0$ 递归
$x=1,y=0$ 回去求解。

证明

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

用 pair 表示

pair<int, int> extgcd(int a, int b) {
  if (!b) return make_pair(1, 0);
  int x, y;
  tie(y, x) = extgcd(b, a % b);
  y -= a / b * x;
  return make_pair(x, y);
}

非递归：

int gcd(int a, int b, int& x, int& y) {
  x = 1, y = 0;
  int x1 = 0, y1 = 1, a1 = a, b1 = b;
  while (b1) {
    int q = a1 / b1;
    tie(x, x1) = make_tuple(x1, x - q * x1);
    tie(y, y1) = make_tuple(y1, y - q * y1);
    tie(a1, b1) = make_tuple(b1, a1 - q * b1);
  }
  return a1;
}

矩阵法：

int exgcd(int a, int b, int &x, int &y) {
  int x1 = 1, x2 = 0, x3 = 0, x4 = 1;
  while (b != 0) {
    int c = a / b;
    std::tie(x1, x2, x3, x4, a, b) =
        std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
  }
  x = x1, y = x2;
  return a;
}