C++最小公倍数（LCM）

最小公倍数（LCM）详解：从生活例子到C++实现

什么是最小公倍数？

两个数的最小公倍数（Least Common Multiple，简称LCM）就是能同时被这两个数整除的最小的正整数。简单来说，就是两个数的“公共倍数”中最小的那个。

举个例子：你和朋友一起跑步，你跑一圈要4分钟，他跑一圈要6分钟。你们同时从起点出发，问多少分钟后你们会再一次同时回到起点？这个时间就是4和6的最小公倍数。因为4的倍数是4、8、12、16……，6的倍数是6、12、18……，共同的倍数里最小的是12，所以答案是12分钟。

再举个生活中的例子：妈妈买了一些糖果，想平均分给小明和小红，每人分的数量必须都是整数。小明每次可以拿4颗，小红每次可以拿6颗。那么妈妈至少需要准备多少颗糖果，才能让两人都正好拿完？答案也是12颗（小明拿3次，小红拿2次）。

最小公倍数和最大公约数的关系

要计算最小公倍数，有一个非常方便的公式：

\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}

其中 GCD 是最大公约数（Greatest Common Divisor）。这个公式的意思是：两个数的乘积等于它们的最小公倍数乘以最大公约数。比如4和6：最大公约数是2，乘积是24，24 ÷ 2 = 12，正好是最小公倍数。

为什么这个公式成立？因为每个数都可以分解成质因数，最小公倍数取所有质因数的最高次幂，最大公约数取所有质因数的公共最低次幂，两者乘起来正好回原两个数的乘积。不过你暂时不用深究，记住这个常用公式就够了。

如何用C++计算最小公倍数？

既然有公式，我们只需要先算出最大公约数，然后代入公式即可。最大公约数可以用之前学过的“辗转相除法”（也称欧几里得算法）来求。代码非常简洁。

注意公式里先乘后除：a * b / gcd(a, b)。如果a和b比较大，比如a=1000000，b=1000000，那么a * b = 1e12，已经超过了C++中int类型的范围（int最大约21亿）。虽然结果在long long范围内，但乘出来的中间结果会溢出。所以一定要先除后乘：a / gcd(a, b) * b，这样中间结果不会太大。另外，为了保险，通常将函数返回值类型设为long long。

常见错误与避免方法

忘记处理a或b为0的情况
如果其中一个数为0，最小公倍数数学上没有定义（或定义为0）。实际编程中，如果输入可能是0，需要先判断。但通常我们只处理正整数，可以忽略。
直接使用int类型导致溢出
刚才已经说过，一定要用long long或先除后乘。
调用gcd时参数顺序影响结果
辗转相除法对任意顺序都有效，但最好养成习惯：gcd(a, b)中如果a<b，算法会自动交换，没问题。
未包含头文件
#include <iostream> 和 using namespace std; 别忘了。

完整可运行代码示例

下面是完整的C++程序，包含了gcd函数和lcm函数，以及一个简单的交互界面。代码中每行变量都加了中文注释，方便理解。

#include <iostream>
using namespace std;

// 计算最大公约数（欧几里得算法）
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;  // 临时变量保存余数
        a = b;             // 更新a为原来的b
        b = temp;          // 更新b为余数
    }
    return a;
}

// 计算最小公倍数（先除后乘防止溢出）
long long lcm(int a, int b) {
    // 先计算 a / gcd(a, b)，再乘以 b，中间结果不会太大
    return (long long)a / gcd(a, b) * b;
}

int main() {
    int x, y;  // 两个输入的正整数
    cout << "请输入两个正整数：";
    cin >> x >> y;

    // 计算并输出最小公倍数
    long long result = lcm(x, y);
    cout << "最小公倍数是：" << result << endl;

    return 0;
}

运行示例：

请输入两个正整数：4 6
最小公倍数是：12

输入12和18：

请输入两个正整数：12 18
最小公倍数是：36

更多思考：当两个数很大时怎么办？

如果两个数都达到几亿，它们的乘积会非常大，long long也可能装不下。这时先除后乘依然有效，因为a / gcd(a, b)会先缩小一个数。但如果你用的是更大的整数类型（比如unsigned long long），依然要注意极限情况。对于竞赛或实际应用，通常题目会指定范围，你按范围选择合适类型即可。