Skip to content

欧几里得算法

2021-08-14

INFO

若无特殊说明,本章涉及的变量皆为正整数。

最大公因数

ab 的最大公因数记作 gcd(a,b),简记为 (a,b)

a,b 有公因数 d,则 amodb=abab 也有因数 d。也就是说,ab 的所有公因数,同时也是 bamodb 的公因数,因此它们的最大公因数也相等。

gcd(a,b)=gcd(b,amodb)

递归到 b=0 时,a 即为 gcd(a,b)

时间复杂度为 O(log(a+b))

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

最小公倍数

ab 的最小公倍数记作 lcm(a,b),简记为 [a,b]

gcd(a,b)=d,则 k1,k2a=k1db=k2d,所以:

lcm(a,b)=k1k2d=k1dk2dd=abgcd(a,b)

时间复杂度为 O(log(a+b))

cpp
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

扩展欧几里得算法

扩展欧几里得算法用于求方程 ax+by=gcd(a,b) 关于 x,y 的解,其中 a,b 是常数。

ax1+by1=gcd(a,b),

bx2+(amodb)y2=gcd(b,amodb),

gcd(a,b)=gcd(b,amodb) 可知:

ax1+by1=bx2+(amodb)y2=bx2+(aabb)y2=bx2+ay2abby2=ay2+b(x2aby2){x1=y2y1=x2aby2

因此,考虑先递归求解 bx+(amodb) y=gcd(a,b),再由其解推出 ax+by=gcd(b,amodb) 的解。

边界条件:当递归到 b=0 时,一定有一组解 {x=1y=0

cpp
struct Set {
    int x, y;
    Set(int x, int y) : x(x), y(y) {}
};

Set exGcd(int a, int b) {       // 求解 ax + by = gcd(a, b)
    if (b == 0)
        return Set(1, 0);
    Set ans = exGcd(b, a % b);  // 先递归求解 bx + (a % b)y = gcd(b, a % b)
    return Set(ans.y, ans.x - (a / b) * ans.y);
}