求两数最小公倍数的通解（通用方法解法）

求两个数a和b的最小公倍数，最常用和最有效的方法是利用它们与最大公约数（Greatest Common Divisor, GCD）之间的关系。

核心公式

两个数的最小公倍数等于这两个数的乘积除以它们的最大公约数。用数学公式表示为：
$$LCM(a,b)=\frac{|a * b|}{GCD(a,b)}$$

其中：

• LCM(a, b)是a和b的最小公倍数
• GCD(a, b)是a和b的最大公约数
• |a*b|表示a和b乘积的绝对值（确保结果为正）。

求解步骤

1. 计算最大公约数(GCD)：首先，你需要一个函数来计算两个数的最大公约数。最经典的算法是欧几里得算法（Euclidean Algorithm），也称为辗转相除法。
   • 欧几里得算法原理： 两个整数 a 和 b（假设 a > b）的最大公约数等于 b 和 a 除以 b 的余数（a % b）的最大公约数。我们不断重复这个过程，直到余数为0，此时的除数就是原始两个数的最大公约数。
2. 应用公式： 计算出 GCD(a, b) 后，直接代入上述核心公式，即可求得最小公倍数。

举例说明

求 12 和 18 的最小公倍数。

1. 求GCD(12, 18)：
   • 18 % 12 = 6
   • 12 % 6 = 0
   • 余数为0，所以GCD(12, 18)=6
2. 计算LCM
   • LCM(12, 18) = (12 * 18) / GCD(12, 18)
   • LCM(12, 18) = 216 / 6
   • LCM(12, 18) = 36

C++ 代码实现

下面是使用 C++ 实现上述逻辑的代码。代码结构清晰，包含一个计算 GCD 的函数和一个计算 LCM 的函数。

#include <iostream>
#include <numeric> // C++17 标准库中包含了 std::gcd 和 std::lcm

// 函数声明
long long gcd(long long a, long long b);
long long lcm(long long a, long long b);

// --- 方法一：手动实现 GCD 和 LCM (推荐，兼容性好) ---

/**
 * @brief 使用欧几里得算法计算最大公约数 (GCD)
 * * @param a 第一个整数
 * @param b 第二个整数
 * @return long long a 和 b 的最大公约数
 */
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/**
 * @brief 使用公式 (a * b) / gcd(a, b) 计算最小公倍数 (LCM)
 * * @param a 第一个整数
 * @param b 第二个整数
 * @return long long a 和 b 的最小公倍数
 */
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) {
        return 0; // 0 和任何数的最小公倍数是 0
    }
    // 为了防止 a * b 溢出，可以先做除法
    // a * (b / gcd(a,b)) 同样有效
    // 使用 std::abs 确保处理负数时结果为正
    return std::abs(a * b) / gcd(a, b); 
}


int main() {
    long long num1, num2;

    std::cout << "请输入两个整数: ";
    std::cin >> num1 >> num2;

    // --- 使用手动实现的函数 ---
    std::cout << "--- 使用手动实现 ---" << std::endl;
    long long result_gcd = gcd(num1, num2);
    long long result_lcm = lcm(num1, num2);
    std::cout << "最大公约数 (GCD) 是: " << result_gcd << std::endl;
    std::cout << "最小公倍数 (LCM) 是: " << result_lcm << std::endl;
    std::cout << std::endl;


    // --- 方法二：使用 C++17 标准库 <numeric> (如果你的编译器支持) ---
    std::cout << "--- 使用 C++17 标准库 ---" << std::endl;
    std::cout << "最大公约数 (GCD) 是: " << std::gcd(num1, num2) << std::endl;
    std::cout << "最小公倍数 (LCM) 是: " << std::lcm(num1, num2) << std::endl;


    return 0;
}