拓展歐幾裡得（求方程整數解）

​

拓展歐幾裡得就是用來求ax+by=gcd(a, b)的所有的整數解。

如果知道了一組特解x0，y0那麼就可以求出它的所有解了。

由歐幾裡得算法有 gcd(a,b) = gcd(b, a%b)

遞歸調用的過程中a和b都不斷縮小，直到b為0，這時a就是gcd（a，b）

a * x1 + b * y1 = g(a,b)

b * x2 + (a%b) * y2 = g(b,a%b)

由于兩個等式右邊的值是相等的，是以有

a * x1 + b * y1 = b * x2 + (a%b) * y2

其中a%b可以換成a-(a/b) * b式子變成了

a * x1 + b * y1 = b * x2 + (a - (a / b) * b) * y2

整理一下

a * x1 + b * y1 = a * y2 + b * (x2 - (a / b) * y2)

用待定系數法

x1 = y2（等式兩邊a的系數相同）

y1 = x2 - (a / b) * y2 （等式兩邊b的系數相同）（向零取整）

如果知道方程b * x2 + (a%b) * y2 = g(b,a%b) 的解x2, y2，就可以得到方程a * x1 + b * y1 = g(a,b) 的解x1,y1了。

對于方程a * x + b * y = gcd(a,b)，不斷的往下變成b * x + (a % b) y = gcd(a,b) ，按照歐幾裡得的過程，b會變成0，即此時方程a * x + b * y = gcd(a,b) 因為b = 0，變成了a * x = gcd(a,b) ，還是由歐幾裡得算法得到，此時a就等于gcd(a,b)，是以得到由原方程往下推了不知道多少次的方程 a * x = gcd(a,b) 來說，得到一個解x = 1, y = 0。現在得到了這個方程的解，再回溯回去，就可以得出原方程 a * x + b * y = gcd(a,b) 的一個特解。

void e_gcd(int a, int b, int &gcd, int &x, int&y)
{
  if (b==0){
    x=1;
    y=0;
    gcd=a;
  }else{
    e_gcd(b, a%b, gcd, y, x);//注意要交換x和y 
    y=y-x*(a/b);//有上面推導出來的公式
    //x1 = y2（等式兩邊a的系數相同）
    //y1 = x2 - (a / b) * y2 （等式兩邊b的系數相同） 
  }
}