1 条题解
-
0
题目分析
本题要求计算三个整数的最小公倍数(LCM)。 题目提示中已经给出了明确的算法步骤和注意事项:
- 先求 a 和 b 的最小公倍数 m,再求 m 和 c 的最小公倍数。
- 求最小公倍数需要用到最大公约数(GCD),公式为:LCM(a, b) = a / GCD(a, b) * b。
- 求 GCD 使用辗转相除法(欧几里得算法)。
- 特别注意:计算 LCM 时必须先除后乘(a / gcd(a, b) * b),这样可有效避免中间结果溢出。
解题思路
- 编写一个
gcd函数,使用辗转相除法求两个数的最大公约数。 - 编写一个
lcm函数,利用公式a / gcd(a, b) * b求两个数的最小公倍数。 - 主函数中读取三个整数 a, b, c。
- 先计算 a 和 b 的最小公倍数
lcm_ab,再计算lcm_ab和 c 的最小公倍数,得到最终结果。 - 输出最终结果,注意末尾换行,前后无多余字符。
易错点提示
- 先除后乘防止溢出:在
lcm函数中,如果写成a * b / gcd(a, b),在a和b较大时(接近 int 上限),a * b会先溢出变成错误的值(虽然最终结果在 int 范围内,但乘积本身会超出)。因此务必写成a / gcd(a, b) * b。 - 辗转相除法细节:GCD 函数的循环条件通常写作
while (b != 0),不断更新a = b, b = a % b,直到b为 0,此时a即为最大公约数。 - 输入输出:题目保证输入为正整数,结果不超过 int 范围。直接使用
int类型即可。输出时不带任何多余提示字符。
参考代码 (C语言)
#include <stdio.h> // 辗转相除法求最大公约数 int gcd(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a; } // 求最小公倍数,先除后乘防止溢出 int lcm(int a, int b) { return a / gcd(a, b) * b; } int main() { int a, b, c; // 读取三个整数 if (scanf("%d %d %d", &a, &b, &c) != 3) { return 0; } // 分步计算:先求 a 和 b 的 LCM,再与 c 求 LCM int lcm_ab = lcm(a, b); int ans = lcm(lcm_ab, c); // 输出结果 printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 632
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 39
- 已通过
- 22
- 上传者
吉公网安备22010402001496号