扩展欧几里得算法

通俗地讲就是辗转相除法。
若有两个数a和b，求两个数的公因数。
可以枚举两个数的因子，复杂度为O(n)，数据大的时候就很慢了。
于是便有了欧几里得算法：gcd(a,b)=gcd(b,a mod b)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公约数
假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等。
复杂度为O(log min(a,b)).

利用欧几里得算法思想求得不定方程 ax+by=gcd(a,b) 的一组解。
原理如下：
设a>b
1）当b=0有 ax=gcd(a,b)=a，即x=1，而y为任意数，为了统一我们令y=0；
2）接下来看一组方程：
方程一 ： ax1+by1=gcd(a,b)
方程二 ： bx2+(a%b)y2=gcd(b,a%b) (方程二由欧几里得算法 gcd(a,b) =gcd(b,a%b) 得到）
两个等式右边相等，所以 ax1+by1 = bx2+(a%b)y2
又a%b=a-floor(a/b)b (这里floor的意思是向下取整，在c++代码中int类型可以不用floor）
得ax1+by1=bx2+[a-floor(a/b)b]y2
在这里把a，b当成未知数，根据多项式恒等定理由x1a+y1b=y2a+[x2-floor(a/b)y2]b可得
x1=y2
y1=[x2-floor(a/b)y2]
由最终解x=1,y=0不断向前推出目标解x1,y1
不难想到利用递归求解，根据上述过程得到以下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;

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

int main()
{
    int x, y, a, b;
    cin >> a >> b;
    cout << "ab最大公约数:" << endl;
    cout << exgcd(a, b, x, y) << endl;
    cout << "x = " << x << "   y = " << y << endl;
    return 0;
}

关于除法逆元，请看其他博客。