求所有同学锻炼周期的最小公倍数,即下一次全员同时锻炼要过多少天。
班上共 n 名同学,第 i 位同学每隔 aᵢ 天锻炼一次。某一天所有人恰好都来锻炼了,求下一次所有同学都来锻炼至少还要过多少天。
lcm(x, y) = x / gcd(x, y) × y——先除后乘,可以有效避免中间结果溢出。最小公倍数最大公约数辗转相除防溢出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n;第二行 n 个正整数 aᵢ |
| 输出 | 最少要过的天数(即 LCM) |
| 含义 | 第 i 位同学的锻炼发生在 aᵢ, 2aᵢ, 3aᵢ, … 天 |
| 目标 | 最小的正数 T,使 T 是每个 aᵢ 的倍数 |
ans = lcm(ans, aᵢ)ans / gcd(ans, aᵢ) * aᵢ,先除后乘逐个累积求 LCM。
把第 1 个数 1 并入:lcm(1, 1) = 1
ans = 1
gcd(1, 2) = 1
lcm(1, 2) = 1 / 1 × 2 = 2
ans = 2
gcd(2, 3) = 1
lcm(2, 3) = 2 / 1 × 3 = 6
ans = 6
验证:第 1 人天天来;第 2 人在第 2、4、6 天来;第 3 人在第 3、6 天来 → 第 6 天三人同来 ✓
这两组数据很能说明 LCM 的含义。
| 样例 | a | LCM | 说明 |
|---|---|---|---|
| 2 | 2, 4, 8, 16 | 16 | 每个数都是前一个的倍数,所以最大那个就是 LCM |
| 3 | 2, 4, 6, 8 | 24 | 4 和 6 的 LCM 是 12,再与 8 求 LCM 得 24 |
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
12 × 8 = 96 再除以 4 得 24——这里 96 还没溢出。但如果 aᵢ 达到 10⁹ 量级,x × y 会到 10¹⁸,恰好接近 long long 上限,再多乘一次就溢出了。写成 x / gcd * y 能把中间值控制住。从左到右依次求 lcm(ans, aᵢ)
ans = ans / __gcd(ans, a[i]) * a[i];——这个顺序能有效减小中间结果,是写 LCM 的标准姿势。把每个 aᵢ 分解,对各质数取指数的最大值再相乘
lcm = ∏ p^(max e_i)。但直接用 gcd 的公式更省事,只有在需要"按质因数分析"时才用分解法。| 方案 | 代码量 | 适用性 |
|---|---|---|
| 累积 LCM | 约 10 行 | 通用 |
| 质因数分解法 | 约 35 行 | 需要质因数视角时 |
输入每位同学的锻炼周期,程序会逐步求最小公倍数。
点按钮开始 →
#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; }
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]) | 求 gcd | C++ 内置函数,等价于辗转相除 |
ans / __gcd(...) * a[i] | 先除后乘 | 避免中间结果溢出 |
long long | 类型 | LCM 可能很大 |
ans * a[i] / __gcd(ans, a[i])(先乘会溢出);② 初值取 0 而不是 1;③ 用 int 存结果。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 6 | 题面样例 1 |
4 | 16 | 题面样例 2:都是倍数关系 |
4 | 24 | 题面样例 3 |
1 | 7 | 只有一位同学,周期就是答案 |
2 | 1 | 都是 1,明天就全员同练 |
3 | 30 | lcm(6,10)=30,lcm(30,15)=30 |
ans * a[i] / gcd 会让中间结果过大而溢出。lcm(0, x) = 0,答案会全错。LCM 的初值应取 1。需要存下 n 个周期(也可以边读边算,省掉数组)。
✅ 运算量极小,瞬间完成。关键是把问题识别成 LCM,以及注意"先除后乘"防溢出。
// 最大公约数(辗转相除) 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 / 乘除的题 |