解题思路

n 名同学上课频率不同（每隔 k 天上一次课），第一天都上课，问最少第几天所有人一起上课。

核心：最小公倍数。

每个同学上课的时间是第 1 天、第 1+k 天、第 1+2k 天……

所有人一起上课，说明这个天数是所有频率的倍数。第一次一起上课（除了第 1 天），就是所有频率的最小公倍数 lcm 天之后。

所以答案 = lcm(所有频率) + 1。

怎么求最小公倍数？

利用公式：lcm(a,b) = a × b ÷ gcd(a,b)。

逐个合并：

• lcm 初始为 1
• 每次读入一个频率 k，更新 lcm = lcm ÷ gcd(lcm,k) × k

gcd 是什么？ 最大公约数，用辗转相除法求。

举例：频率 3、2、4

• LCM(3,2,4) = 12
• 答案 = 12 + 1 = 13

参考代码

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    int n, k;
    cin >> n;

    long long lcm = 1;
    for (int i = 0; i < n; i++) {
        cin >> k;
        lcm = lcm / gcd(lcm, k) * k;  // 合并最小公倍数
    }

    cout << lcm + 1;  // 除第一天外
    return 0;
}

复杂度分析

• 时间复杂度：O(N log M)，每次求 gcd
• 空间复杂度：O(1)