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);
}

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

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

• 那么可以在递归求Gcd过程中，计算ax + by = Gcd(a,b)了：
  依据上面的$ax+by = ay_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;
  }

通过以上推导可得到一组特解x0
$ax_1+by_1 = ax_2+by_2$ ,同时除以Gcd(a,b)
$a’(x_1-x_2) = b’(y_2-y_1)$
除以Gcd(a,b)后 $a’ b’$ 互素
则$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可计算得出