GESP 题解库 / 5 级题解 / [GESP样题 五级] 小杨的锻炼 · 第 20 / 23 题
GESP样题 五级 · B3941 · 简单

小杨的锻炼

求所有同学锻炼周期的最小公倍数,即下一次全员同时锻炼要过多少天。

📊
n 名同学
数据规模
🔢
long long
数值类型
⚡
O(n log A)
时间复杂度
🎯
最小公倍数 LCM
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

班上共 n 名同学,第 i 位同学每隔 aᵢ 天锻炼一次。某一天所有人恰好都来锻炼了,求下一次所有同学都来锻炼至少还要过多少天。

💡
人话翻译:这题就是求所有周期的最小公倍数(LCM)。因为"同时锻炼"意味着经过的天数必须同时是每个 aᵢ 的倍数。关键公式:lcm(x, y) = x / gcd(x, y) × y——先除后乘,可以有效避免中间结果溢出。

🔍 关键词提取

最小公倍数最大公约数辗转相除防溢出

已知条件

项目说明
输入第一行 n;第二行 n 个正整数 aᵢ
输出最少要过的天数(即 LCM)
含义第 i 位同学的锻炼发生在 aᵢ, 2aᵢ, 3aᵢ, … 天
目标最小的正数 T,使 T 是每个 aᵢ 的倍数

需要解决的问题

02
思维导图
整理解题思路的全貌
📅 求所有周期的最小公倍数
🧠 模型转化
第 i 人每 aᵢ 天一次
同时锻炼 ⟺ 天数同时是各 aᵢ 的倍数
所以答案是 LCM
结论:求 LCM(a₁…aₙ)
🔧 单个 LCM
lcm(x,y) = x / gcd(x,y) × y
先除后乘防溢出
gcd 用辗转相除
O(log A)
🔄 累积
ans 初始为 1
依次 ans = lcm(ans, aᵢ)
或从 a₁ 开始
n 个数的 LCM = 反复两两求
⚠️ 易错点
用 int 溢出
写成 x * y / gcd(先乘会溢出)
gcd 写成递归但未处理 0
以为答案是乘积 Σ 而非 LCM
03
样例手算推导
三个样例的 LCM 计算

🧮 样例 1:a = [1, 2, 3],答案 6

逐个累积求 LCM。

1
初始 ans = 1

把第 1 个数 1 并入:lcm(1, 1) = 1

ans = 1

2
并入 2

gcd(1, 2) = 1

lcm(1, 2) = 1 / 1 × 2 = 2

ans = 2

3
并入 3

gcd(2, 3) = 1

lcm(2, 3) = 2 / 1 × 3 = 6

ans = 6

验证:第 1 人天天来;第 2 人在第 2、4、6 天来;第 3 人在第 3、6 天来 → 第 6 天三人同来 ✓

🧮 样例 2 与样例 3 的对比

这两组数据很能说明 LCM 的含义。

样例aLCM说明
22, 4, 8, 1616每个数都是前一个的倍数,所以最大那个就是 LCM
32, 4, 6, 8244 和 6 的 LCM 是 12,再与 8 求 LCM 得 24
1
样例 3 逐步算

ans = 2

并入 4:gcd(2,4)=2 → lcm = 2/2×4 = 4

并入 6:gcd(4,6)=2 → lcm = 4/2×6 = 12

并入 8:gcd(12,8)=4 → lcm = 12/4×8 = 24

✅ ans = 24

🔑
注意"先除后乘"的重要性:以 lcm(12, 8) 为例,12 × 8 = 96 再除以 4 得 24——这里 96 还没溢出。但如果 aᵢ 达到 10⁹ 量级,x × y 会到 10¹⁸,恰好接近 long long 上限,再多乘一次就溢出了。写成 x / gcd * y 能把中间值控制住。
04
解法对比
累积 LCM vs 分解质因数求 LCM

⚔️ 解法对比

🟢 累积 LCM(推荐) 推荐

从左到右依次求 lcm(ans, aᵢ)

  • 时间 O(n log A)
  • 代码 10 行
  • 不需要分解质因数
  • 最直接
💡
注意先除后乘:ans = ans / __gcd(ans, a[i]) * a[i];——这个顺序能有效减小中间结果,是写 LCM 的标准姿势。

🟠 分解质因数后取最大指数

把每个 aᵢ 分解,对各质数取指数的最大值再相乘

  • 理论正确但代码长
  • 需要分解每个数
  • 还要处理大质数
  • 完全没必要
⚠️
两者等价:lcm = ∏ p^(max e_i)。但直接用 gcd 的公式更省事,只有在需要"按质因数分析"时才用分解法。

📈 性能对比

方案代码量适用性
累积 LCM约 10 行通用
质因数分解法约 35 行需要质因数视角时
05
算法流程图
逐个累积求最小公倍数
开始读入 n 和数组 aans = 1i 从 0 到 n−1ans = ans / gcd(ans, a[i]) × a[i]n 个数都并入了吗?输出 ans结束i 加 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📅 全员同练天数计算器

输入每位同学的锻炼周期,程序会逐步求最小公倍数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long a[100];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    long long ans = 1;                        // LCM 的单位元是 1
    for (int i = 0; i < n; i++) {
        // 先除后乘,避免 ans * a[i] 这一步溢出
        ans = ans / __gcd(ans, a[i]) * a[i];
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么初始值取 1 而不是 0?因为 LCM 的"单位元"是 1——lcm(1, x) = x。如果取 0,lcm(0, x) 在数学上是 0,整个答案就变成 0 了。注意区分:求 gcd 时初值取 0(因为 gcd(0,x)=x),求 lcm 时初值取 1。

📖 关键几行怎么看

代码作用为什么这样写
long long ans = 1初值lcm 的单位元是 1
__gcd(ans, a[i])求 gcdC++ 内置函数,等价于辗转相除
ans / __gcd(...) * a[i]先除后乘避免中间结果溢出
long long类型LCM 可能很大
⚠️
三个坑:① 写成 ans * a[i] / __gcd(ans, a[i])(先乘会溢出);② 初值取 0 而不是 1;③ 用 int 存结果。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
1 2 3
6题面样例 1
4
2 4 8 16
16题面样例 2:都是倍数关系
4
2 4 6 8
24题面样例 3
1
7
7只有一位同学,周期就是答案
2
1 1
1都是 1,明天就全员同练
3
6 10 15
30lcm(6,10)=30,lcm(30,15)=30
✅
自查清单:① 初值是 1 吗?② 先除后乘了吗?③ 用 long long 吗?

🚨 易错点清单

⚠️
先乘后除:写成 ans * a[i] / gcd 会让中间结果过大而溢出。
⚠️
初值取 0:lcm(0, x) = 0,答案会全错。LCM 的初值应取 1。
⚠️
用 int:LCM 可能超出 int 范围,用 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n log A)
空间复杂度
O(n)
n
本题不大
每次 gcd
O(log A)

时间怎么算的?

空间都用在哪?

需要存下 n 个周期(也可以边读边算,省掉数组)。

✅ 运算量极小,瞬间完成。关键是把问题识别成 LCM,以及注意"先除后乘"防溢出。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 最大公约数(辗转相除)
long long gcd(long long a, long long b) {
    while (b) { long long t = a % b; a = b; b = t; }
    return a;
}

// 最小公倍数:必须先除后乘
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// 多个数的 LCM
long long ans = 1;
for (int i = 0; i < n; i++) ans = lcm(ans, nums[i]);

// 记忆要点
// gcd 的单位元 = 0   (gcd(0, x) = x)
// lcm 的单位元 = 1   (lcm(1, x) = x)

// 溢出检查(如果需要)
if (a / gcd(a,b) > LLONG_MAX / b) { /* 会溢出 */ }

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
LCM 模型同时发生 ⟺ 取最小公倍数周期问题、相遇问题、齿轮咬合
辗转相除求 gcd 的高效方法所有数论题目
先除后乘避免中间结果溢出所有涉及 lcm / 乘除的题
🌟
思考题:如果题目改成"求上一次全员同时锻炼是几天前",答案会变吗?(提示:不会变——因为"同时锻炼"的事件是周期性发生的,周期恰好是 LCM。所以"下一次"和"上一次"的间隔都是 LCM。这体现了周期性问题中"往返时间对称"的特点。)