计算最小公倍数（LCM）

思路分析

最小公倍数（LCM）可通过最大公约数（GCD）计算得出。数学公式为：
[ \text{LCM}(a, b) = \frac{|a \times b|}{\text{GCD}(a, b)} ]

1. 计算GCD：使用欧几里得算法递归求解两数的最大公约数。
2. 处理零值：若任一数为零，LCM定义为0（数学上无意义，但程序需特判）。
3. 防溢出：先除后乘避免大数运算溢出。

代码实现

#include <iostream>
#include <cstdlib> // 用于abs函数

// 计算最大公约数（GCD）
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 计算最小公倍数（LCM）
int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0; // 处理零值
    return abs(a / gcd(a, b) * b);   // 先除后乘防溢出
}

int main() {
    int num1, num2;
    std::cout << "输入两个整数: ";
    std::cin >> num1 >> num2;
    
    std::cout << "LCM: " << lcm(num1, num2) << std::endl;
    return 0;
}

关键点说明

• 递归终止条件：GCD计算中当b为0时返回a。
• 绝对值处理：使用abs确保结果非负，兼容负数输入。
• 输入验证：实际应用中可添加输入类型检查。

复杂度分析

• 时间复杂度：欧几里得算法为(O(\log(\min(a, b))))。
• 空间复杂度：递归调用栈深度为(O(\log(\min(a, b))))。

扩展建议

• 多数值LCM：迭代计算多个数的LCM，如lcm(a, lcm(b, c))。
• 大数优化：若处理极大整数，可使用更高效的二进制GCD算法。

实现方法

方法一：利用最大公约数（GCD）计算

最小公倍数（LCM）可通过最大公约数（GCD）推导，公式为：
$$\text{LCM}(a,b)=\frac{|a\times b|}{\text{GCD}(a,b)}$$
使用C++标准库中的std::gcd（需C++17或更高版本）：

#include <numeric>
#include <cstdlib>

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

方法二：迭代法

通过逐步增加较大数的倍数，验证是否能被另一个数整除：

int lcm(int a, int b) {
    int max_num = (a > b) ? a : b;
    while (true) {
        if (max_num % a == 0 && max_num % b == 0) {
            return max_num;
        }
        ++max_num;
    }
}

方法三：递归结合GCD

递归实现GCD后计算LCM，适用于教学或特定算法需求：

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

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

方法四：STL扩展（多数值LCM）

对容器中的多个数计算LCM，使用std::accumulate：

#include <vector>
#include <numeric>

int lcm_of_range(const std::vector<int>& nums) {
    return std::accumulate(nums.begin(), nums.end(), 1, 
        [](int x, int y) { return std::lcm(x, y); });
}

注意事项

• 输入需处理非负数或零值，避免除零错误。
• 大数运算时需考虑整数溢出，可改用long long类型。
• C++17以下版本需手动实现gcd函数。