【学习笔记】欧几里得与扩展欧几里得

学习笔记, 欧几里得与扩展欧几里得

Gcd

欧几里得算法又称辗转相除法，用于计算两个整数的最大公约数.

引理：
求整数 a、b 的最大公约数，表示成 gcd(a,b)，设 r = a % b，则 gcd(a, b) = gcd(b, a % b).

证明:
a = kb + r, r = a % b.
假设 c 是 a、b 的公约数，则 c | a, c | b, r = a - kb，因此 c | r.
因此 c 也是 (b, a % b) 的公约数.
c | b, c | r, a = kb + r.
所以 c 也是 (a, b) 的公约数.
既然 (a, b）与 (b, a % b) 的公约数相等，其最大公约数也必然相等，得证.
(gcd(a, 0) = a)

exGcd

扩展欧几里得算法，一般用来求解不定方程、线性同余方程、模的逆元等.

可以根据裴蜀定理那一课的证明来学一学，这里就不再多说，不过仍有值得一提的：以下程序求出 ax + by = gcd(a, b) 的一组特解 x0, y0，并返回 a，b 的最大公约数 d。对于更为一般的方程 ax + by = c，它有解当且仅当 d | c。我们可以先求出 x0, y0，然后令 x0, y0 同乘以 c / d，就得到了 ax + by = c 的一组特解 (c / d)x0, (c / d)y0。

事实上，方程 ax + by = c 的通解可以表示为：x = (c / d)x0 + k(b / d), y = (c / d)y0 + k(a / d)，其中 k 取遍整数集合。

CODE:

1
2
3
4
5
6
7
void exGcd(int a, int b, int &x, int &y) {
    if (b == 0) {x = 1, y = 0; return a;}
    int d = exGcd(b, a % b, x, y);
    int z = x;
    x = y, y = z - y * (a / b);
    return d;
}