gcd(a,b)和exgcd(a,b,x,y)

​

​gcd()​

​：

int gcd(int a,int b)
{
    if(b) return gcd(b,a%b);
    else return a;
}      

當然也可以使用頭檔案​

​<algorithm>​

​​自帶的函數​

​__gcd(a,b)​

​

​

​exgcd(a,b,x,y)​

​：

int exgcd(int a,int b,int &x,int &y)
{
    int gcd;
    if(b){
        gcd=exgcd(b,a%b,y,x);
        y-=a/b*x;
    }
    else gcd=a,x=1,y=0;
    return gcd;
}      

證明：

假設有

①\(ax_1+by_1=gcd(a,b)\)

②\(a'x_2+b'y_2=gcd(a,b)\)

先假設②是在①的下面，也就是說，在遞歸順序中②是先執行完的。

我們由\(gcd(a,b)\)的代碼實作過程可以很容易得到：

\(a'=b,b'=a\%b=a-a/b*b\)

代入②式得\(bx+(a-a/b*b)y_2=gcd(a,b)\)，整理一下，\(ay_2+b(x_2-a/b*y_2)=gcd(a,b)\)

跟①式進行對照，即可得出\(\begin{cases}x_1=y_2\\y_1=x_2-a/b*y_2 \end{cases}\)

即得到了\(x\)和\(y\)的遞推關系