GCD 与 LCM：欧几里得算法

欧几里得算法的推导

为什么 gcd(a,b) = gcd(b, a%b) 成立？令 a = qb + r，若 d | a 且 d | b，则 d | r = a - qb；反之若 d | b 且 d | r，则 d | a。所以 a 和 b 的公因子集合 = b 和 r 的公因子集合，GCD 相等。

package main

import "fmt"

// 递归版（经典）
func gcd(a, b int) int {
    if b == 0 { return a }
    return gcd(b, a%b)
}

// 迭代版（避免栈溢出）
func gcdIter(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

// 最小公倍数：lcm(a,b) = a*b / gcd(a,b)
// 先除后乘，防止溢出
func lcm(a, b int) int {
    return a / gcd(a, b) * b
}

func main() {
    // 分数化简：48/36 = (48/gcd) / (36/gcd) = 4/3
    a, b := 48, 36
    g := gcd(a, b)
    fmt.Printf("%d/%d 化简为 %d/%d\n", a, b, a/g, b/g)

    // 任务调度：A 每 12s 触发，B 每 8s 触发，多久同时触发？
    fmt.Println("最小公倍数:", lcm(12, 8))  // 24

    // 验证欧几里得是对的
    fmt.Println(gcd(252, 105))  // 21
    fmt.Println(gcd(0, 5))      // 5（边界）
}

扩展欧几里得与贝祖定理

贝祖定理：存在整数 x, y 使得 ax + by = gcd(a, b)。扩展欧几里得算法不只返回 GCD，还返回这组系数 (x, y)。当 gcd(a, m) = 1 时，ax ≡ 1 (mod m)，x 就是 a 的模逆元。

package main

import "fmt"

// 扩展欧几里得：返回 (gcd, x, y)，满足 a*x + b*y = gcd
func extGCD(a, b int) (int, int, int) {
    if b == 0 {
        return a, 1, 0
    }
    g, x1, y1 := extGCD(b, a%b)
    // 回溯：a*y1 + b*(x1 - (a/b)*y1) = g
    return g, y1, x1 - (a/b)*y1
}

func main() {
    g, x, y := extGCD(252, 105)
    fmt.Printf("gcd=%d, x=%d, y=%d\n", g, x, y)  // gcd=21
    fmt.Println(252*x + 105*y)  // 21 ✓

    // 用 extGCD 求模逆元：3 * x ≡ 1 (mod 11)
    _, inv, _ := extGCD(3, 11)
    inv = (inv%11 + 11) % 11
    fmt.Println(inv, 3*inv%11)  // 4  1 ✓
}

应用：最简分数与音乐节拍

欧几里得算法是人类历史上第一个有记录的算法，它比零的发明还早 600 年。

— 算法导论