扩展欧几里得

\(ax_1+by_1=gcd(a,b)\)

\(bx_2+(a \mod b)y_2=gcd(b,a \mod b)\)

\(\because gcd(a,b)=gcd(b,a\mod b)\)

\(\therefore ax_1+by_1=bx_2+(a\mod b)y_2\)

\(\because a\mod b=a-\lfloor \frac{a}{b}\rfloor b\)

\(\therefore ax_1+by_1=bx_2+ay_2-\lfloor \frac{a}{b}\rfloor by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)\)

\(\therefore x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2,x1，y1为当前层，x2,y2为递归的下一层的值\)

\(\because 最后一层,a=g,b=0,ax+by=g\)

\(\therefore 设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;
}

扩展欧几里得

原文：https://www.cnblogs.com/VIrtu0s0/p/11987789.html