luogu-B3941 [GESP样题 五级] 小杨的锻炼

GESP C++ 五级初等数论考点练习，难度⭐⭐★☆☆。洛谷难度等级普及−

luogu-B3941 [GESP样题 五级] 小杨的锻炼

题目要求

题目描述

小杨的班级里共有 $n$ 名同学，每位同学都有各自的锻炼习惯。具体来说，第 $i$ 位同学每隔 $a_i$ 天就会进行一次锻炼（也就是说，每次锻炼会在上一次锻炼的 $a_i$ 天后进行）。某一天，班上的 $n$ 名同学恰好都来进行了锻炼。他们对此兴奋不已，想要计算出下一次所有同学都来锻炼，至少要过多少天。但他们不会计算，你能帮帮他们吗？

输入格式

第一行一个整数 $n$，表示同学的数量。
第二行 $n$ 个用空格隔开的正整数，依次为 $a_0, a_1, …, a_{n-1}$。

输出格式

输出一个整数，表示下一次所有同学都来锻炼，至少要过多少天。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

6

输入输出样例 #2

输入 #2

4
2 4 8 16

输出 #2

16

输入输出样例 #3

输入 #3

4
2 4 6 8

输出 #3

24

说明/提示

样例 1 解释

第一位同学每天都锻炼；第二位同学每 $2$ 天锻炼一次；第三位同学每 $3$ 天锻炼一次。因此，$6$ 天之后，三位同学都会进行锻炼。在此之前，第二位同学只会在第 $2, 4$ 天进行锻炼，第三位同学只会在第 $3$ 天进行锻炼，他们都无法相遇。

样例 2 解释

第四位同学每 $16$ 天锻炼一次，而 $16$ 天后也恰好是前三位同学锻炼的日子。

数据规模与约定

• 对 $20\%$ 的数据，$n = 2$。
• 对 $50\%$ 的数据，$n = 4$。
• 对 $100\%$ 的数据，$2 \leq n \leq 10$，$1 \leq a_i \leq 50$。

题目分析

解题思路

题目要求的是“下一次所有同学都来锻炼”的最少天数，本质就是求所有同学锻炼周期的最小公倍数（LCM）。

1. 每位同学每隔 $a_i$ 天锻炼一次，意味着他们的锻炼日期分别是 $0, a_i, 2a_i, 3a_i, \dots$ 天。
2. 所有人再次同时锻炼的那一天，必须是每个 $a_i$ 的倍数，因此就是所有 $a_i$ 的最小公倍数。
3. 计算多个数的最小公倍数，可以从左到右两两合并：
   lcm(a,b,c) = lcm(lcm(a,b), c)，以此类推。
4. 两数最小公倍数用公式：
   lcm(x,y) = x * y / gcd(x,y)，其中 gcd 用欧几里得算法即可。

复杂度

• 每次 gcd 计算是 $O(log max(a_i))$；
• 共 $n-1$ 次 lcm 合并，总体 $O(n log max(a_i))$；
• 数据范围 $n≤10, a_i≤50$，完全无压力。

边界注意

• 若 $n=1$，答案就是唯一的 $a_0$；
• 乘法过程可能超 int，用 long long 存储中间结果。

示例代码

#include <iostream>
#include <cmath>

// 全局数组：存储每位同学的锻炼周期，最多支持 15 人
int nums[15];

// 计算两个正整数的最大公约数（Greatest Common Divisor）
// 采用欧几里得递归算法
long long gcd(long long a, long long b) {
    if (b == 0) {          // 当余数为 0 时，a 即为 gcd
        return a;
    }
    return gcd(b, a % b); // 递归：gcd(a,b) = gcd(b, a mod b)
}

// 计算两个正整数的最小公倍数（Least Common Multiple）
// 利用公式：lcm(a,b) = a*b / gcd(a,b)
// 先取两数较大/较小者，避免乘法溢出
long long lcm(long long a, long long b) {
    long long l = std::max(a, b); // 较大数
    long long s = std::min(a, b); // 较小数
    return l * s / gcd(l, s);    // 返回最小公倍数
}

int main() {
    int n;                     // 同学数量
    std::cin >> n;             // 读入 n
    for (int i = 0; i < n; i++) {
        std::cin >> nums[i];   // 读入每位同学的锻炼周期
    }
    // 初始结果设为第一个同学的周期
    long long result = nums[0];
    // 依次与后面同学的周期求 lcm，得到全员同时锻炼的最小天数
    for (int i = 1; i < n; i++) {
        result = lcm(result, nums[i]);
    }
    std::cout << result << std::endl; // 输出答案
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

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

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

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

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