C++ 三个数最小公倍数暴力法实现及优化建议

好的，这是一个典型的求最小公倍数（LCM）的问题。我们一步步来帮你完成代码。 ### 1. 补充 `lcm` 函数 `lcm` 函数用于计算两个数的最小公倍数。你的方法是**从一个数开始递增，直到找到第一个能同时被 x 和 y 整除的数**。 **while 循环的条件**应该是：**当前数 t 不能同时被 x 和 y 整除**，即： ```cpp while (t % x != 0 || t % y != 0) ``` **完整后的函数：** ```cpp int lcm(int x, int y) { int t = x; // 从 x 开始尝试，也可以从较大的数开始，但这里直接用了 x // 当 t 不能被 x 整除 或者 不能被 y 整除时，继续循环 while (t % x != 0 || t % y != 0) { t++; } return t; } ``` --- ### 2. 计算三个数的最小公倍数 已知两个数的 LCM 后，三个数的 LCM 可以通过**先求前两个数的 LCM，再与第三个数求 LCM** 得到。 在 `main` 函数的 `//计算并输出三个数字的最小公倍数` 处，添加： ```cpp int result = lcm(k, c); // 用前两个数的 LCM 与第三个数再求一次 LCM cout << result << endl; ``` --- ### 3. 完整代码 ```cpp #include <iostream> using namespace std; int lcm(int x, int y) { int t = x; while (t % x != 0 || t % y != 0) { t++; } return t; } int main() { int a, b, c; cin >> a >> b >> c; int k = lcm(a, b); int result = lcm(k, c); cout << result << endl; return 0; } ``` --- ### 4. 测试样例 **样例1：** 输入：`1 2 3` 计算过程： - lcm(1, 2) = 2 - lcm(2, 3) = 6 输出：`6` ✅ **样例2：** 输入：`2 3 4` - lcm(2, 3) = 6 - lcm(6, 4) = 12 输出：`12` ✅ --- ### 5. 🚀 进阶建议 - **性能优化**：上面的 `lcm` 函数是暴力递增法，当数字较大时（如 10000 和 9999），会循环很多次。**推荐使用数学公式**： `lcm(a, b) = a * b / gcd(a, b)` gcd 可以用辗转相除法（欧几里得算法）实现，效率高得多。 - **使用公式的改进版**（推荐在生产环境使用）： ```cpp int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } int lcm_fast(int a, int b) { return a / gcd(a, b) * b; // 先除后乘，防止溢出 } ``` - **溢出防范**：`a * b` 可能超出 `int` 范围，建议使用 `long long` 或先除后乘。 - **多数字扩展**：求多个数（如 N 个数）的最小公倍数，循环调用 `lcm` 即可： ```cpp int result = arr[0]; for (int i = 1; i < n; i++) { result = lcm(result, arr[i]); } ``` --- ### 6. 📚 常见陷阱 - **while 条件写错**：容易写成 `t % x == 0 && t % y == 0`，这样循环会在第一次不成立时立刻停止，导致结果错误。 - **初始值 t 设置**：如果从 1 开始，效率更低；从较大的数开始（如 `max(x, y)`）可以稍微优化。 - **输入格式**：三个整数用空格隔开，题目已保证，无需额外处理。 --- ######[AI写代码神器 | 964点数解答 | 2026-06-20 19:12:53]