数学：最大公约数

Bellala · 2024-06-25 21:29:30 · 算法·理论

1. 欧几里得算法

几个常识

• 若 d|x 且 d|y 则 d|x+y 且 d|x-y 且 d|ax+by
• \gcd(a, 0) = a

辗转相减（更相减损术）

证明思路：证明左右两边的因子完全相同（这是很基本的数学证明方法）。

int gcd(int a, int b) { //注意b=0时的情况
    while (a != b) {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

辗转相减很少用。改良版本的辗转相减（Stein 算法）可能在求大整数的最大公约数时更快。

辗转相除（欧几里得算法）

证明：a \% b = a - \lfloor \frac ab\rfloor b = a - kb。

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

复杂度 O(\log)，因为 a\%b 每次至少把 a 减半。

多个数的最大公约数：\gcd(a,b,c,d)。

最小公倍数

证明思路：考虑 a\cdot b,\mathrm{lcm}(a,b),\gcd(a,b) 的唯一分解定理形式。

2. 裴蜀定理

问题：求解不定方程 ax+by=c，其中 a,b 是不全为 0 的整数，x,y 是未知数。

根据上面的“常识”，若 d|a 且 d|b 则一定有 d|c，那么 \gcd(a,b)|c 也就是说，如果这个不定方程有解，则 c 一定是 \gcd(a,b) 的倍数。

裴蜀定理

若 a,b 是不全为 0 的整数，则存在整数 x,y，使得 ax+by=\gcd(a,b)。

3. 扩展欧几里得算法

问题：求 ax + by = gcd(a, b) 的一组解。

注意到右边相等，所以 a x_1 + b y_1 = b x_2 + (a\%b) y_2

注意到 a \% b = a - \lfloor \frac ab \rfloor b

则 a x_1 + b y_1 = a y_2 + b (x_2-\lfloor \frac ab\rfloor y_2)

我们只用找一组可行解，所以可以让 x_1 = y_2, y_1 = x_2-\lfloor \frac ab\rfloor y_2

int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) { //递归结束
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); //得到y1=x2,x1=y2，不要被位置迷惑
    y -= a / b * x; // y1 -= (a/b) y2，注意x已经变成了y2
    return d;
}

解的性质：欧几里得得到的解绝对值最小且范围不大 （不会爆int，且只需调整一次）

准确范围在 USACO guide 及 Wikipedia 有说明：

所有的解：x-\frac bd k, y+\frac ad k （证明：假设有两个解，……）

应用：求解线性同余方程的非负整数解

做法：改写为不定方程 ax + my = b，然后用 exgcd 求解。

int solve(int a, int b, int m) {
    int x, y, d = exgcd(a, m, x, y); // ax + my = d
    if (b % d != 0) return -1; //无解
    x = b / d * x % m;
    if (x < 0) x += m; //注意得到的x有可能是负数
    return x;
}