扩展欧几里得

· · 算法·理论

定义：

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展, 其目的是为了找到一个整数解关于未知数 x 和 y 的线性同余方程 ax+by=c 的整数解。

推理过程：

ax_1+by_1=gcd(b,a\bmod b) bx_2+(a\bmod b)y_2=gcd(b,a\bmod b)

由欧几里得定理可知：gcd(a,b)=gcd(b,a\bmod b)

\therefore ax_1+by_1=bx_2+(a\bmod b)y_2 \because a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b \therefore ax_1+by_1=bx_2+(a-\lfloor\frac{a}{b}\rfloor\times b)y_2 \therefore ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2 \therefore ax_1+by_1=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2) \therefore x_1=y_2, y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2

将 x_2 , y_2 不断代入递归求解直到 b=0 ，递归 x=1 , y=0 回去求解。

代码实现：

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