欧几里得算法

知识总结

最大公约数（GCD）

两个整数的最大公约数是能同时整除它们的最大正整数。

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

核心思想：gcd(a, b) = gcd(b, a % b)，直到 b = 0 时，a 即为结果。

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

示例：gcd(48, 18)

• gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6

最小公倍数（LCM）

lcm(a, b) = a × b / gcd(a, b)

int lcm(int a, int b) {
    return a / gcd(a, b) * b; // 先除后乘防溢出
}

相关性质

• gcd(a, 0) = a
• gcd(a, 1) = 1
• 如果 gcd(a, b) = 1，则 a 和 b 互质
• gcd(a, b) × lcm(a, b) = a × b

C++内置函数

C++17 起可直接使用 __gcd(a, b) 或 中的 gcd(a, b)。