G1020 [GESP202506 一级] 值日 题解

难度：2（GeekPi教学评定）；知识点：最小公倍数、周期问题、枚举。

解题思路

两人的值日周期分别为m与n，再次同一天值日需要经过同时为二者倍数的正天数，答案是最小公倍数。一级基础写法可从m开始每次增加m，直到能被n整除；C++17参考代码调用lcm。

为什么正确

共同值日的间隔必须同时是m与n的倍数，其中最小正数就是首次再次相遇的间隔。

易错点

题目问再次一起值日，不能输出0；m与n有公因数时答案小于m*n。

复杂度

时间：O(log min(m,n))；枚举倍数写法为O(n)；额外空间：O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;
    cin>>m>>n;
    cout<<lcm(m,n);
}

来源与说明

本题解为配套教学整理，非官方题解。题库使用自行生成的测试数据，6个测试点。