欧几里得算法(euclidean)

欧几里得算法又称辗转相除法，是指用于计算两个非负整数 a，b 的最大公约数。

1. 判断 b 是否为 0，若为 0，则返回 a
2. 否则返回 gcd(b, a % b)

证明

1. 设$b$与$a \% b$的最大公约数为$c$
2. 则$b = k_1 \times c$, $a \% b = k_2 \times c$, 且$k1$,$k2$必互质
3. $a \% b = a - k \times b = k_2 \times c$,可得$a = k_2 \times c + k \times k_1 \times c = (k_2 + k \times k_1) \times c$
4. 由上可得$a$与$b$必有一因数$c$
5. 设$k1$与$k_2 + k \times k_1$的最大公约数是$d$
6. 设令$k_2 = x$, $k_1 = y$, 则$gcd(x + k \times y, y) = d$
7. 设$y = m \times d$, $x + k \times y = n \times d$, 则$x = n \times d - k \times m \times d = (n - k \times m) \times d$
8. 则$b = k_1 \times c = m \times d \times c$
9. 则$a \% b = k_2 \times c = (n - k \times m) \times d \times c$
10. 由于$gcd(b, a \% b) = c$, 则$d = 1$
11. 由此可得$a$

扩展欧几里得

已知$a$,$b$,求$a \times x + b \times y = gcd(a, b)$的$x$,$y$一个解

1. 设$a \times x + b \times y = gcd(a, b) = b \times x + (a \% b) \times y$
2. $b \times x + (a \% b) \times y = b \times x + (a - k \times b) \times y = b \times x + a \times y - k \times b \times y = a \times y + b \times (x - k \times y) = a \times y + b \times (x - floor(a / b) \times y)$
3. 带入上一层得$x = y_1$, $y = x_1 - floor(a / b) \times y_1$
4. 由于$a \% b = n \% 0$则$a \times x + b \times y = gcd(a, b) = n \times x + 0 \times y$, 可求得一解$x = 1$, $y = 0$
5. 从最里层开始往上回溯即可得解

核心代码

/**
 * 欧欧几里得算法
 * 返回a与b的最大公约数
 */
export function gcd(a: number, b: number) {
    if (b) return gcd(b, a % b);
    return a;
}
/**
 * 扩展欧几里得算法
 * 已知a,b
 * 求a * x + b * y == gcd(a,b)中,x与y的一个解
 */
export function ex_gcd(
    a: number,
    b: number,
): {
    ans: number;
    x: number;
    y: number;
} {
    if (b === 0) return { ans: a, x: 1, y: 0 };
    const res = ex_gcd(b, a % b);
    [res.x, res.y] = [res.y, res.x - Math.floor(a / b) * res.y];
    return res;
}

/**
 * 返回a与b的最大公倍数
 */
export function lcm(a: number, b: number) {
    return (a * b) / gcd(a, b);
}