擴充歐幾裡德知識（一）

了解歐幾裡德，那麼擴充歐幾裡德就能很容易了解了，對任意a，b（a>b），我們列出這樣一個式子： a*x+b*y=gcd(a,b);

不要覺得擴充歐幾裡德很牛逼，它就是一個算x，y的一個方法，隻是在上面gcd中多了處理x，y的步驟

我們這樣來想：

已知目前的一個狀态：a1  b1  x1  y1,    a1*x1+b1*y1=gcd(a1,b1),注意這裡的a1，b1是求gcd（a，b）中的一個狀态，

假設 （a1，b1）是由（a0，b0）轉移過去的

那麼：   a1=b0 ;     b1=a0%b0=a0-k*b0 （k=int(a0/b0)）;    gcd(a0,b0)=gcd(a1,b1);

代入a1*x1+b1*y1=gcd(a1,b1),    變化成：b0*x1+(a0-k*b0)*y1=gcd(a1,b1)=gcd(a0,b0);

a0*y1+b0*(x1-k*y1)=gcd(a0,b0);

這樣可以得到： x0=y1;  y0=x1-k*y1;(了解這個過程了麼，由目前狀态可以算出上一狀态的x，y，即目前狀态可以由它的下一個狀态的x，y得到)。

int exGcd(int a,int b,int &x,int &y)
{
  if(b==0)
  {
    x=1;
    y=0;
    return a;// 此時a是最開始（a,b）的最大公約數，那麼  gcd（a,b）*1+ 0*0=gcd(a,b),肯定對的，在這裡，我認為，y可以為任何值都對
  }
  
  int d=exGcd(b,a%b,y,x);
  y-=a/b*x;
  return d;//傳回最大公約數
}      

需要注意一點的就是方程得到的解不止一個是一個通解！

關于求解二進制一次不定方程ax+by=c

    首先，如果c不是gcd(a,b)的倍數，方程顯然無解。

擴充歐幾裡得求解的是ax+by=gcd(a,b)=1的可行解，但是題目中并沒有說c與a,b互質之類的條件，是以需要在開始時兩邊同時除以gcd(a,b)。

設d=gcd(a,b)

設a'=a/d,b'=b/d,c'=c/d,

則下面需要求解a'x+b'y=c'的整數解，而gcd(a',b')=1，

則我們隻需求a'x+b'y=1的可行解

直接使用擴充歐幾裡得，得到(x',y'),則最終解為x'*c',y'*c'設為(x0,y0)。

現在得到了一組可行解，但是如何得到通解呢？

将(x0,y0)代入ax+by=c，則有

a*(x0)+b*(y0)=c

通過拆添項，可有：

a*(x0+1*b)+b*(y0-1*a)=c

a*(x0+2*b)+b*(y0-2*a)=c

a*(x0+3*b)+b*(y0-3*a)=c

……

a*(x0+k*b)+b*(y0-k*a)=c  (k∈Z)

至此，我們得到了通解的方程

x=x0+k*b

y=y0-k*a  (k∈Z)