Extend_Eculid扩展欧几里得算法：ax + by = Gcd(a,b)

感谢优秀博客：扩展欧几里德算法详解
先回顾一下欧几里得算法求Gcd(a, b)

int Gcd(int a, int b){
    if(b == 0)
        return a;
    return(b, a%b);
}
Copy

对于ax + by = Gcd(a,b)的求解，注意a，b要求为非负整数，并且该方程一定有解

先推导出一组特解$x_0$吧
欧几里得算法利用的等式:$Gcd(a,b)=Gcd(b,a$
于是这里有：$ax+by=bx+(a$
$b{x}_1+(a$
$=b{x}_1+(a-a/b\ast b)y_1=a{y}_1+b(x_1-(a/b)y_1)$

• 那么可以在递归求Gcd过程中，计算ax + by = Gcd(a,b)了：
  依据上面的$ax+by=a{y}_1+b(x_1-(a/b)y_1)$
  令上一深度的x为下一深度的y，上一深度的y为下一深度的x-(a/b)y
  递归的出口即b = 0,x = 1, y = 0
  ——————————————————————————————————

  void Extend_Eculid(ll a, ll b, ll &x, ll &y)
  {               //求解ax + by = Gcd(a,b) 
      if(!b)
      {
          x = 1; y = 0;
          return;
      }
      // Extend_Eculid(b, a%b, x, y);
      // int t = x;
      // x = y;
      // y = t-(a/b)*y;
      // 等于下面语句
      Extend_Eculid(b, a%b, y, x);
      y = y - a/b*x;
  }
  Copy

通过以上推导可得到一组特解x0
$a{x}_1+b{y}_1=a{x}_2+b{y}_2$ ,同时除以Gcd(a,b)
$a^{\prime }(x_1-x_2)=b^{\prime }(y_2-y_1)$
除以Gcd(a,b)后 $a^{\prime }{b}^{\prime }$ 互素
则$x_1-x_2=t\times b,y_2-y_1=t\times a$(t=…-2,-1,0,1,2…)
得通解 $x=x_0+t\times b/Gcd(a,b)$ (t=…-2,-1,0,1,2…)
y的解根据x可计算得出