貝祖定理&擴充歐幾裡得

貝祖定理是一個關于最大公約數的定理：

若a，b是整數，那麼對于任意整數x，y，ax+by是gcd(a,b)的倍數，且一定存在x，y使得ax+by=gcd(a,b)成立。

定理内容較為簡單，但光看定理的内容貌似沒有太大用處，我們應該着手解決一下如何求出x，y，于是，可以引出擴充歐幾裡得。

擴充歐幾裡得

當求ax+by=gcd(a,b)時，我們可以用一組特解x0，y0來表示x和y的通解：

x = x 0 + b / g c d ( a , b ) ∗ t x=x_0+b/gcd(a,b)*t x=x0​+b/gcd(a,b)∗t

y = y 0 + a / g c d ( a , b ) ∗ t y=y0+a/gcd(a,b)*t y=y0+a/gcd(a,b)∗t

這裡的“/”為向下取整。

試圖找出相鄰兩狀态之間的關系：

目前狀态有：a，b，以及一組解x，y

下一狀态有：a，a%b，以及一組解x1，y1

因為a%b=a-(a/b)*b，

帶入可得：

g c d ( a , b ) = b x 1 + a y 1 − ( a / b ) ∗ b y 1 gcd(a,b)=bx_1+ay_1-(a/b)*by_1 gcd(a,b)=bx1​+ay1​−(a/b)∗by1​

= a y 1 + b ∗ ( x 1 − a / b ∗ y 1 ) =ay_1+b*(x_1-a/b*y_1) =ay1​+b∗(x1​−a/b∗y1​)

于是可以發現：

x = y 1 , y = x 1 − ( a / b ) ∗ y 1 x=y_1,y=x_1-(a/b)*y_1 x=y1​,y=x1​−(a/b)∗y1​

便可由下一狀态通過遞歸得到現在的狀态。

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