扩展欧几里得

扩展欧几里得

求解$a∗x+b∗y=gcd(a,b)$

时间复杂度 $O(logn)$

$${100*x} + {87*y}=1 \\87*\underbrace{(x+y)}_\text{ x2 } + 13*\underbrace{x}_\text{y2}=1\\ 13*\underbrace{(6*x2+y2)}_\text{x3} + 9*\underbrace{x2}_\text{y3}=1\\ 9*\underbrace{(x3+y3)}_\text{x4} + 4*\underbrace{x3}_\text{y4}=1\\ 4*\underbrace{(2*x4+y4)}_\text{x5} + \underbrace{x4}_\text{y5}=1\\ \underbrace{(4*x5+y5)}_\text{x6}=1 此时x_{6}=1,y_{6}=0;$$

即

解$ax+by=1$

有$(b*\lfloor\frac{a}{b}\rfloor+a\%b)*x+b*y=1$

$$b*\underbrace{(\lfloor\frac{a}{b}\rfloor*x+y)}_\text{x'} +a\%b* \underbrace{x}_\text{y'}=1 则a\to b,b \to a\% b$$

$bx'+a\%b*y'=1$

$x=y', y=x'-\lfloor\frac{a}{b}\rfloor*y'$，递归即可

求$a,b$

$a\%b=a-\lfloor\frac{a}{b}\rfloor*b$

由归纳假设存在u',v'，使得$u'*b+v'*(a\%b)=d$

即$u'*b+v'(a-\lfloor\frac{a}{b}\rfloor*b)=d$

$v'*a+(u'-\lfloor\frac{a}{b}\rfloor*v')*b=d$

于是就得到了a,b的解

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    /*
    //1
    int xx, yy;
    int d = exgcd(b, a % b, xx, yy);
    x = yy;
    y = xx - (a / b) * yy;
    return d;
    */
​
    /*
    //2
    int d= exgcd(b, a % b, x, y);
    int k = y;
    y = x - (a / b) * y;
    x = k;
    return d;*/
​
    //3
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

实际应用：

通解为

$$x=x_{0}+\frac{b}{gcd(a.b)}*t,y=y_{0}-\frac{a}{gcd(a.b)}*t$$

求一元二次线性方程ax+by=c的整数解

先求出$ax+by=gcd(a,b)$的解，然后把解乘以$\frac{c}{gcd(a,b)}$就得到了原方程的解，如果$\frac{c}{gcd(a,b)}$不是整数，说明原方程没有整数解（贝祖定理）

在求出特解后，通解为

$$x=x_{0}+\frac{b}{gcd(a.b)}*t,y=y_{0}-\frac{a}{gcd(a.b)}*t$$

若要求x的最小非负整数解

$x=(x_{0}\%\frac{b}{gcd(a.b)}+\frac{b}{gcd(a.b)})\%\frac{b}{gcd(a.b)}$，若要求此时的y，则可以通过$ax+by=gcd(a,b)$来求

int ex_gcd(int a, int b, int& x, int& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  int d = ex_gcd(b, a % b, x, y);
  int temp = x;
  x = y;
  y = temp - a / b * y;
  return d;
}
​
bool liEu(int a, int b, int c, int& x, int& y) {
  int d = ex_gcd(a, b, x, y);
  if (c % d != 0) return 0;
  int k = c / d;
  x *= k;
  y *= k;
  return 1;
}