exgcd详解

1.exgcd是什么？

exgcd大名扩展欧几里得算法，用来求形如 (gcd(a,b) = ax + by) 的方程的通解。

---

2.推导

引理：存在 (x,yin mathbb Z) 使得 (gcd(a,b) = ax + by)（裴蜀定理，请自行百度）

当 (b=0) 时，(gcd(a,b)=a)，此时 (x_1=1)， (y_1=0)

当 (b ot=0) 时，

由题，(ax+by=gcd(a,b)=gcd(b,amod b)=bx_2+(amod b)y_2 ①)

又因 (amod b=a-lfloor dfrac{a}{b} floor b)

则 (ax+by=bx_2+(a-alfloor dfrac{a}{b} floor b)y_2)

(ax+by=bx_2+ay_2-lfloor dfrac{a}{b} floor by_2)

(ax+by=ay_2+bx_2-blfloor dfrac{a}{b} floor y_2)

(ax+by=ay_2+b(x_2-lfloor dfrac{a}{b} floor y_2) ②)

将 (②) 式对比 (①) 式，得出：

方程 (gcd(a,b) = ax + by) 的通解为 (x=y_2) ， (y=x_2-lfloor dfrac{a}{b} floor y_2)

//公式是我一个字一个字手敲的，要敲断了……

---

3.代码实现

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