To boldly go where no one has gone before.

【学习笔记】拓展欧几里得算法

2019-03-31 23:05:37


拓展欧几里得$(exgcd)$算法是用于解决$ax+by=gcd(a,b)$的一种算法。

我们设:$$ax_1+by_1=d=gcd(a,b)\cdots1 $$$$bx_2 +(a\%b)y_2=gcd(b,a\%b)\cdots2$$ 由$\%$运算性质可得:$$gcd(a,b)=gcd(b,a\%b)$$ 则可得:$$ax_1+by_1=bx_2+(a\%b)y_2$$ 而在C++中,$/$表示整除运算,由$\%$的运算性质可得:$$\Rightarrow ax_1+by_1=bx_2+(a-a/b\times b)y_2$$$$\Rightarrow ax_1+by_1=ay_2+b(x_2-a/b\times y_2)\;\;(\text{欧几里得算法})$$ 显然可以得出:$$\Rightarrow x_1=y_2,\;y_1=x_2-a/b\times y_2$$ 特别地,我们定义当$b=0$时,$gcd(a,b)=a$,也就是辗转相除法中当$a\mod b=r=0$时,$gcd(a,b)=b$。此时$x=1,y=0$。这是递归边界。

当$ax+by=1$,$gcd(a,b)=d=1$,所以:$$(ax)\mod b=(1-by)\mod b=1 \mod b$$$$\Rightarrow x \text{的解就是a关于模b的逆元}.$$$$\text{同理可得}y\text{的解就是b关于模a的逆元}.$$ 这种方法仅可用于$a\equiv 1(\mod b)$的情况!


代码

#include<bits/stdc++.h>
using namespace std;

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

int main() {
    int a, b, x, y;
    scanf("%d%d", &a, &b);
    int gcd = ExGcd(a, b, x, y);
    printf("x=%d y=%d gcd=%d\n", x, y, gcd);
    return 0;
}