【GESP 一级】洛谷 B4355 值日 题解

一、题目概述

本题是GESP 2025 年 6 月一级认证真题，对应洛谷题号 B4355，是入门阶段的经典数学应用题，核心是求两个数的最小公倍数。

题目可以简化为：已知小杨每m天值日一次，小红每n天值日一次，今天他们一起值日，问至少多少天后会再次同一天值日？

• 样例输入：4、6 → 输出 12（4 和 6 的最小公倍数是 12）

---

二、核心考察点（GESP 一级官方考点）

这道题覆盖了 GESP 一级的多个核心考点，同时引入了简单的数论知识：

表格

考点	考察内容	难度
多变量输入输出	读取两个整数并输出结果	⭐
循环结构	使用循环实现求最大公约数 / 最小公倍数	⭐⭐
数论基础	理解最小公倍数的概念，掌握 “最小公倍数 = 两数乘积 ÷ 最大公约数” 的公式	⭐⭐⭐
算法逻辑	用辗转相除法（欧几里得算法）或枚举法实现求最大公约数	⭐⭐⭐

---

三、解题思路分析

1. 核心数学概念

要解决这个问题，我们需要先理解两个关键概念：

• 最大公约数（GCD）：能同时整除m和n的最大正整数，比如 4 和 6 的最大公约数是 2。
• 最小公倍数（LCM）：同时是m和n倍数的最小正整数，比如 4 和 6 的最小公倍数是 12。

两者的关系公式：

​这道题的答案，就是求m和n的最小公倍数。

2. 两种实现方法（新手友好）

方法 1：枚举法（暴力求最小公倍数，逻辑直观）

从max(m,n)开始往上找，第一个同时能被m和n整除的数，就是最小公倍数。

int ans = max(m, n); // 从较大的数开始枚举 while (true) { if (ans % m == 0 && ans % n == 0) { break; } ans++; } cout << ans << endl;

优点：逻辑简单，容易理解；缺点：当数字较大时效率低，但本题m,n≤100，完全够用。

方法 2：辗转相除法（求最大公约数，再算最小公倍数）

先求m和n的最大公约数，再用公式计算最小公倍数，效率更高。辗转相除法求 GCD 的核心逻辑：

1. 用较大数除以较小数，得到余数；
2. 把除数作为新的被除数，余数作为新的除数；
3. 重复步骤 1-2，直到余数为 0，此时的除数就是最大公约数。

// 辗转相除法求最大公约数 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } // 计算最小公倍数：(m*n)/gcd(m,n) int lcm = m * n / gcd(m, n);

---

四、易错点提醒（考试避坑）

1. 乘法溢出问题（本题无影响，养成好习惯）题目中m,n≤100，m*n最大为 10000，在int范围内，不会溢出；如果数字更大，建议先除后乘：(m / gcd(m,n)) * n，避免溢出。

2. 枚举法的循环起点枚举法一定要从max(m,n)开始，而不是从 1 开始，否则会做很多无用计算，效率极低。

3. 辗转相除法的参数顺序辗转相除法不要求a > b，因为第一次循环会自动调整顺序（比如gcd(4,6)会自动变成gcd(6,4)），但写代码时注意循环条件b != 0。

4. 边界值测试

   • 当m和n相等时：如 m=5，n=5 → 最小公倍数是 5；
   • 当m和n互质时：如 m=3，n=4 → 最小公倍数是 12；
   • 当其中一个数是 1 时：如 m=1，n=7 → 最小公倍数是 7。

---

五、完整 C++ 代码（两种写法，可直接提交）

写法 1：枚举法（新手友好，逻辑清晰）

#include <iostream> #include <algorithm> // 用于max函数 using namespace std; int main() { int m, n; cin >> m >> n; // 从较大的数开始枚举，找第一个同时被m和n整除的数 int ans = max(m, n); while (true) { if (ans % m == 0 && ans % n == 0) { break; } ans++; } cout << ans << endl; return 0; }

写法 2：辗转相除法（高效，推荐掌握）

#include <iostream> using namespace std; // 辗转相除法求最大公约数 int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } int main() { int m, n; cin >> m >> n; // 计算最小公倍数：(m*n)/最大公约数 int lcm = m * n / gcd(m, n); cout << lcm << endl; return 0; }

---

六、总结

这道题的核心是理解最小公倍数的概念，并掌握对应的计算方法，是 GESP 一级中为数不多涉及简单数论的题目。

学会这道题，你不仅能解决 “值日问题”，还能举一反三：

• 比如 “公交车发车问题”：1 路车每 5 分钟发一次，2 路车每 8 分钟发一次，同时发车后，多久会再次同时发车？答案就是 5 和 8 的最小公倍数 40。
• 比如 “周期重合问题”：两个循环事件的再次重合时间，都是求最小公倍数的应用场景。

掌握辗转相除法，对后续学习数论相关题目也非常有帮助！