【GESP/CSP】编程武器库-4, 最大公约数和最小公倍数

在五级题目（【GESP】C++五级练习（初等数论考点） luogu-B3941 [GESP样题 五级] 小杨的锻炼）中，涉及到最大公约数和最小公倍数的计算，需要用到数论中的基本概念和算法。这部分既是五级考试大纲中明确要求的内容(【GESP】C++五级考试大纲知识点梳理, (1) 初等数论)，又是编程考试中常见的、可复用的功能函数。因此，在我和孩子的学习过程中，已要求将这部分知识，纳入“武器库”中。

当前武器库清单

分类	功能	教程
字符判断	判断是否为数字(0-9)	【GESP/CSP】编程武器库-1, 字符类型判断
字符判断	判断是否为字母(a-z/A-Z)	【GESP/CSP】编程武器库-1, 字符类型判断
字符判断	判断是否为大写字母(A-Z)	【GESP/CSP】编程武器库-1, 字符类型判断
字符判断	判断是否为小写字母(a-z)	【GESP/CSP】编程武器库-1, 字符类型判断
进制转换	十进制和十六进制转换	【GESP/CSP】编程武器库-2, 十进制转换十六进制
进制转换	十进制和十六进制转换	【GESP/CSP】编程武器库-3, 十六进制转换十进制

本人也是边学、边实验、边总结。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

---

在 C++ 中，从 C++17 开始，标准库已经内置了用于计算 最大公约数（GCD） 和 最小公倍数（LCM） 的函数，包含在numeric头文件中。但是由于CCF GESP考试要求使用 C++11 标准(-std=c++11)，因此我们不能直接使用这两个函数，需要掌握手动实现的方法。

手动实现的理论，是基于欧几里得算法和最大公约和最小公倍的基础公式，这部分内容已在文章(【GESP】C++五级考试大纲知识点梳理, (1) 初等数论)中详细介绍过。这里就不再赘述。下面直接给出代码的具体实现。

一、最大公约数（GCD）

根据欧几里得算法，最大公约数的计算可以通过循环和递归，两种方法实现。代码分别如下：

递归实现（推荐）

/**
 * @brief 计算两个整数的最大公约数（GCD）——递归实现
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最大公约数
 */
int gdc2(int a, int b) {
    int l = std::max(a, b); // 取较大值作为被除数
    int s = std::min(a, b); // 取较小值作为除数
    if (s == 0) {
        return l;           // 若除数为0，则最大公约数为被除数
    }
    return gdc2(s, l % s);  // 递归：用除数和余数继续计算
}

循环实现

/**
 * @brief 计算两个整数的最大公约数（GCD）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最大公约数
 */
int gcd1(int a, int b) {
    // 确保 a 和 b 中的较大值作为被除数，较小值作为除数
    int l = std::max(a, b);
    int s = std::min(a, b);
    // 欧几里得算法：反复用余数替换除数，直到余数为 0
    while (s != 0) {
        int tmp = s;   // 暂存当前除数
        s = l % s;     // 计算余数，作为下一轮的被除数
        l = tmp;       // 上一轮除数变为下一轮的被除数
    }
    // 当余数为 0 时，l 即为最大公约数
    return l;
}

其实，聪明的你可能已经发现，不论是循环实现和递归实现，其实并不需要判断两个数a和b的大小，因为取模运算 % 的规则天然能处理两种情况：

1. 如果 a ≥ b a % b 得到正常的余数，小于 b。 下一轮就自动变成 gcd(b, a % b)。

2. 如果 a < b a % b == a（因为 a 无法整除 b）。 下一轮：

   t = a % b = a;
   a = b;
   b = a;   // 即原来的 a
   

   相当于自动把两数“交换”了。 下一次循环就恢复成“大的在前，小的在后”的正常状态。

循环亦如此，你可以自己推导一下。

---

二、最小公倍数

根据公式直接推导计算即可。

/**
 * @brief 计算两个整数的最小公倍数（LCM）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最小公倍数
 */
int lcm(int a, int b) {
    // 利用公式：lcm(a,b) = a * b / gcd(a,b)
    return a * b / gcd1(a, b);
}

---

最后给出整体调用验证代码

#include <iostream>
#include <cmath>

/**
 * @brief 计算两个整数的最大公约数（GCD）——循环实现
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最大公约数
 */
int gcd1(int a, int b) {
    // 欧几里得算法：反复用余数替换除数，直到余数为 0
    while (s != 0) {
        int tmp = s;
        s = l % s;
        l = tmp;
    }
    return l;
}

/**
 * @brief 计算两个整数的最大公约数（GCD）——递归实现
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最大公约数
 */
int gdc2(int a, int b) {
    if (s == 0) {
        return l;           // 若除数为0，则最大公约数为被除数
    }
    return gdc2(s, l % s);  // 递归：用除数和余数继续计算
}

/**
 * @brief 计算两个整数的最小公倍数（LCM）
 * @param a 第一个整数
 * @param b 第二个整数
 * @return 返回 a 和 b 的最小公倍数
 */
int lcm(int a, int b) {
    // 利用公式：lcm(a,b) = a * b / gcd(a,b)
    return a * b / gcd1(a, b);
}

int main() {
    int a, b;
    std::cin >> a >> b;
    std::cout << gcd1(a, b) << std::endl;
    std::cout << gdc2(a, b) << std::endl;
    std::cout << lcm(a, b) << std::endl;
    return 0;
}

---

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

GESP 学习专题站：GESP WIKI

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

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

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

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