拓展欧几里得

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

证明

扩展欧几里得算法\(:(Extended Euclidean algorithm, EXGCD)\)

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

\(ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_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;
}