luogu-B4355 [GESP202506 一级] 值日

GESP C++一级，2025年6月真题，基础运算和循环语句，难度★☆☆☆☆。

luogu-B4355 [GESP202506 一级] 值日

题目要求

题目描述

小杨和小红是值日生，负责打扫教室。小杨每 $m$ 天值日一次，小红每 $n$ 天值日一次。今天他们两个一起值日，请问至少多少天后，他们会再次同一天值日？

输入格式

第一行，一个正整数 $m$，表示小杨的值日周期；

第二行，一个正整数 $n$，表示小红的值日周期。

输出格式

一行，一个整数，表示至少多少天后他们会再次同一天值日。

输入输出样例 #1

输入 #1

4
6

输出 #1

12

说明/提示

对于所有测试点，保证 $1 \leq m, n \leq 100$。

题目分析

解题思路

本题的解题思路如下：

1. 问题本质：

   • 输入两个正整数 $m$ 和 $n$，分别表示小杨和小红的值日周期
   • 需要计算他们下一次同时值日的最小天数

2. 解题关键：

   • 核心思路 - 最小公倍数：
     1. 两个人同时值日的天数必须同时满足：
        • 能被小杨的值日周期 $m$ 整除
        • 能被小红的值日周期 $n$ 整除
     2. 这实际上就是求两个数的最小公倍数(LCM)
        • 可以通过循环从较大值开始查找
        • 也可以通过 C++ 标准库中的 std::lcm 函数（C++17及以上版本，不符合GESP考试要求:-std=c++11）直接计算最小公倍数，或使用 std::gcd 函数计算最大公约数后，通过公式 LCM = (a × b) ÷ GCD(a,b) 计算

3. 复杂度分析：

   • 时间复杂度：$O(min(m,n))$，需要循环查找或计算最大公约数
   • 空间复杂度：$O(1)$，只需要存储几个整数变量

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>

int main() {
    // 声明变量n和m用于存储输入的两个值日周期
    int n,m;
    // 从标准输入读取两个整数
    std::cin >> n >> m;
    // 找出两个周期中的较大值作为循环起点
    int big = n > m ? n : m;
    // 从较大值开始循环，直到找到符合条件的天数
    for (int i = big; ;i++) {
        // 如果当前天数能同时被两个周期整除，说明是他们再次同时值日的日子
        if (i % n == 0 && i % m == 0) {
            // 输出结果并结束循环
            std::cout << i;
            break;
        }
    }
    return 0;
}        

利用lcm函数示例（需-std=c++17以上，不推荐，不符合GESP官方C++ 编译等级要求）

#include <iostream>
#include <numeric>

int main() {
    // 声明整型变量n和m，用于存储两个人的值日周期
    int n,m;
    // 从标准输入读取两个值日周期
    std::cin >> n >> m;
    // 使用C++标准库的lcm函数计算最小公倍数并输出
    std::cout << std::lcm(n,m);
    // 程序正常结束
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号