8.2 公倍数与公因数

利用辗转相除法，我们可以很方便地求得两个数的最大公因数（greatest common divisor，GCD）；将两个数相乘再除以最大公因数即可得到最小公倍数（least common multiple, LCM）。

C++

int gcd(int a, int b) { 
    return b == 0 ? a : gcd(b, a % b); 
}

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

Python

def gcd(a: int, b: int) -> int:
    return a if b == 0 else gcd(b, a % b)

def lcm(a: int, b: int) -> int:
    return (a * b) // gcd(a, b)

进一步地，我们也可以通过扩展欧几里得算法（extended gcd）在求得 a 和 b 最大公因数的同时，也得到它们的系数 x 和 y，从而使 ax + by = gcd(a, b)。因为 Python 中 int 只能按值传递，我们可以用一个长度固定为 1 的 list() 来进行传递引用的操作。

C++

int xGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int x_inner, y_inner;
    int gcd = xGCD(b, a % b, x_inner, y_inner);
    x = y_inner, y = x_inner - (a / b) * y_inner;
    return gcd;
}

Python

def xGCD(a: int, b: int, x: List[int], y: List[int]) -> int:
    if b == 0:
        x[0], y[0] = 1, 0
        return a
    x_inner, y_inner = [0], [0]
    gcd = xGCD(b, a % b, x_inner, y_inner)
    x[0], y[0] = y_inner, x_inner - (a / b) * y_inner
    return gcd