🧮 B3941 [GESP样题 五级] 小杨的锻炼 教程

（✨图文+图标+样式增强版）

---

🎯 一、问题分析

🔍 题目目标：找出所有同学下一次同时锻炼的最少天数。

📌 关键点：

• 每位同学在 a[i] 天后重复锻炼。
• 所有人都在同一时间出现 → 求所有周期的 最小公倍数（LCM）。

🔢 举个栗子🌰：

• 同学 A：每 2 天锻炼一次
• 同学 B：每 3 天锻炼一次
  👉 下次一起锻炼是第 6 天（2 和 3 的 LCM）

---

🧮 二、算法思路

1️⃣ 最小公倍数 LCM

属性	内容
定义	能被多个整数整除的最小正整数
公式	$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}$

🔹 计算流程图：

输入 a, b
→ 计算 GCD(a, b)
→ LCM = a * b / GCD

---

2️⃣ 最大公约数 GCD

🔁 欧几里得算法（辗转相除法）：

while (b != 0) {
    a, b = b, a % b;
}
return a;

🔷 示例：GCD(12, 18) = 6

---

3️⃣ 多个数的 LCM

🧾 逐对计算法：

LCM(a[0], a[1]) → res
res = LCM(res, a[2])
...
最终得到全体 LCM

📊 示例：[2, 4, 6, 8]

• LCM(2, 4) = 4
• LCM(4, 6) = 12
• LCM(12, 8) = 24

---

📦 三、C++ 实现代码

#include <iostream>
#include <vector>
using namespace std;

long long gcd(long long a, long long b) {
    while (b != 0) {
        swap(a, b);
        b = a % b;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // 防止溢出
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    long long result = a[0];
    for (int i = 1; i < n; ++i) {
        result = lcm(result, a[i]);
    }

    cout << result << endl;
    return 0;
}

---

🛠️ 四、代码详解

✅ gcd 函数

• 使用 while 循环实现欧几里得算法。
• 时间复杂度：$O(\log(\min(a, b)))$

✅ lcm 函数

• 先除后乘防止中间值过大导致溢出。
• 返回两个数的最小公倍数。

✅ 主函数逻辑

1. 输入人数 n 和数组 a[]
2. 初始化 result = a[0]
3. 依次与其余数字求 LCM
4. 输出最终结果

---

⏱️ 五、复杂度分析

类型	描述
⏱️ 时间复杂度	$O(n \cdot \log M)$，其中 M 是最大周期（≤50）
💾 空间复杂度	$O(n)$，用于存储输入数组

---

🧪 六、样例解析

📌 样例 1

输入：
3
1 2 3
输出：
6

🧠 解析：

• LCM(1, 2) = 2
• LCM(2, 3) = 6

---

📌 样例 2

输入：
4
2 4 8 16
输出：
16

🧠 解析：

• 所有数都是前一个的倍数 → 最终 LCM 是最大值 16

---

📌 样例 3

输入：
4
2 4 6 8
输出：
24

🧠 解析：

• LCM(2, 4) = 4
• LCM(4, 6) = 12
• LCM(12, 8) = 24

---

⚠️ 七、常见问题 & 注意事项

🔁 溢出处理

• 使用 long long 类型
• 计算顺序为 a / gcd * b，避免先乘再除造成溢出

🧩 输入含 1 的情况

• LCM(x, 1) = x，不影响最终结果

🔄 周期重复的情况

• LCM(x, x) = x，不会影响最终答案

---

🎯 八、总结

✅ 核心知识点：

• 最大公约数（GCD）
• 最小公倍数（LCM）
• 多个数的 LCM 计算方法

💡 应用场景拓展：

• 多人日程同步
• 车辆调度系统
• 游戏角色技能冷却重叠判断

📚 推荐学习路径：

• 学习欧几里得算法
• 掌握 C++ STL 中的 vector 使用
• 练习 LeetCode 上的 LCM/GCD 相关题目

---

🎨 九、附加资源（图表+工具）

📊 图表说明

周期数组	LCM 结果	解释
[2, 3]	6	最小能被 2 和 3 整除的数
[2, 4, 8]	8	所有数是前面的倍数
[2, 4, 6, 8]	24	逐对计算得出

---

🛠️ 工具推荐

工具名称	功能
WolframAlpha	在线计算 LCM/GCD
Visual Studio Code	C++ 编辑器
LeetCode	刷题平台

---

🧠 学习建议

阶段	推荐内容
新手	数论基础 + 辗转相除法
进阶	LCM 应用场景扩展
高手	多线程/异步任务中的周期同步问题

---

📅 最后更新时间：2025年5月22日 21:56

🎉 祝你刷题愉快，GESP 顺利通关！🚀

B3941 [GESP样题 五级] 小杨的锻炼 教程

---

一、问题分析

题目要求找出所有同学下一次同时锻炼的最少天数。每位同学的锻炼周期为 $a_i$ 天，因此他们会在 $a_i$ 的倍数天进行锻炼。要让所有同学再次同时锻炼，我们需要找到所有 $a_i$ 的 最小公倍数（LCM）。

例如：

• 如果同学 A 每 2 天锻炼一次，同学 B 每 3 天锻炼一次，则他们每 6 天（2 和 3 的最小公倍数）会同时锻炼。

---

二、算法思路

1. 最小公倍数（LCM）

• 定义：最小公倍数是多个整数的公倍数中最小的那个。
• 计算公式：$$\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)} $$其中，$\text{GCD}$ 是最大公约数。

2. 最大公约数（GCD）

• 欧几里得算法（辗转相除法）：
  • 如果 $b = 0$，则 $\text{GCD}(a, b) = a$。
  • 否则，递归计算 $\text{GCD}(b, a \mod b)$。

3. 多个数的最小公倍数

• 对于多个数的最小公倍数，可以逐对计算：$$\text{LCM}(a_1, a_2, ..., a_n) = \text{LCM}(\text{LCM}(...\text{LCM}(\text{LCM}(a_1, a_2), a_3)...), a_n) $$

---

三、C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 计算最大公约数（GCD）
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算最小公倍数（LCM）
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // 先除后乘避免溢出
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 初始结果设为第一个数
    long long result = a[0];
    
    // 依次计算所有数的LCM
    for (int i = 1; i < n; ++i) {
        result = lcm(result, a[i]);
    }
    
    cout << result << endl;
    
    return 0;
}

---

四、代码解释

1. GCD 函数

• 使用欧几里得算法（辗转相除法）计算两个数的最大公约数。
• 例如：gcd(12, 18) 返回 6。

2. LCM 函数

• 利用公式 LCM(a, b) = a / GCD(a, b) * b 计算最小公倍数。
• 先进行除法再乘法可以减少溢出的风险。

3. 主函数

1. 读取输入：
   • 读取同学数量 $n$。
   • 读取每个同学的锻炼周期 $a_0, a_1, ..., a_{n-1}$。
2. 初始化结果：
   • 初始结果为第一个同学的周期。
3. 逐对计算 LCM：
   • 遍历剩余的周期，依次计算当前结果与每个周期的 LCM。
4. 输出结果：
   • 输出最终的最小公倍数。

---

五、复杂度分析

• 时间复杂度：
  • GCD 的时间复杂度为 $O(\log(\min(a, b)))$。
  • 总体时间复杂度为 $O(n \log M)$，其中 $M$ 是 $a_i$ 的最大值（不超过 50）。
• 空间复杂度：$O(n)$，用于存储输入的周期数组。

---

六、示例解析

样例 1

输入：

3
1 2 3

输出：

6

解析：

• 计算 LCM(1, 2) 得到 2。
• 再计算 LCM(2, 3) 得到 6。
• 因此，6 天后所有同学会再次同时锻炼。

样例 2

输入：

4
2 4 8 16

输出：

16

解析：

• 所有数的 LCM 是最大的那个数 16，因为每个数都是前一个的倍数。

样例 3

输入：

4
2 4 6 8

输出：

24

解析：

• 计算 LCM(2, 4) = 4。
• LCM(4, 6) = 12。
• LCM(12, 8) = 24。
• 因此，24 天后所有同学会再次同时锻炼。

---

七、常见问题与注意事项

1. 溢出问题：

   • 使用 long long 类型可以避免大多数溢出问题。
   • 在计算 a / gcd(a, b) * b 时，先除后乘可以防止中间结果过大。

2. 输入中的 1：

   • 如果某个同学的周期为 1（每天锻炼），则不会影响最终结果，因为 LCM(x, 1) = x。

3. 重复的周期：

   • 如果多个同学的周期相同，重复计算不会影响结果，因为 LCM(x, x) = x。

---

八、总结

这道题的核心是理解如何通过 最小公倍数 解决周期性问题。通过分步计算所有数的最小公倍数，可以高效地找到所有同学再次同时锻炼的最少天数。

这道题主要涉及的知识点和算法是最大公约数（GCD）和最小公倍数（LCM）。解题的关键在于理解每个同学的锻炼周期，并计算出所有周期的最小公倍数。

知识点分析

1. 最大公约数（GCD）：两个或多个整数的最大公约数是能够同时整除它们的最大正整数。例如，GCD(12, 18) = 6。

2. 最小公倍数（LCM）：两个或多个整数的最小公倍数是能够被它们全部整除的最小正整数。LCM可以通过GCD计算：LCM(a, b) = |a×b| / GCD(a, b)。

3. 多个数的LCM：计算多个数的LCM时，可以递归地计算：LCM(a, b, c) = LCM(LCM(a, b), c)。

C++ 解决方案

下面是解决该问题的C++代码：

#include <iostream>
#include <vector>
using namespace std;

// 计算两个数的最大公约数（GCD）
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 计算两个数的最小公倍数（LCM）
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b; // 先除后乘避免溢出
}

int main() {
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    // 初始结果设为第一个数
    long long result = a[0];
    
    // 依次计算所有数的LCM
    for (int i = 1; i < n; ++i) {
        result = lcm(result, a[i]);
    }
    
    cout << result << endl;
    
    return 0;
}

代码解释

1. GCD函数：使用欧几里得算法（辗转相除法）计算两个数的最大公约数。

2. LCM函数：利用公式 LCM(a, b) = a / GCD(a, b) * b 计算最小公倍数。先进行除法再乘法可以减少溢出的风险。

3. 主函数：

   • 读取输入的同学数量和每个同学的锻炼周期。
   • 初始化结果为第一个同学的周期。
   • 遍历剩余的周期，依次计算当前结果与每个周期的LCM。
   • 输出最终结果。

复杂度分析

• 时间复杂度：O(n × log(max(a)))，其中n是同学数量，max(a)是最大的锻炼周期。这主要由GCD的计算决定。

• 空间复杂度：O(n)，主要用于存储输入的锻炼周期数组。

这个算法能够高效地处理题目给定的数据范围（n ≤ 10，a_i ≤ 50）。