最大公约数（GCD）和最小公倍数（Least Common Multiple，LCM）研究整除的性质，非常古老，在2000多年前就得到了很好的研究。由于简单易懂，有较广泛的应用，它们是竞赛中频繁出现的考点。
一、最大公约数（GCD）
1、GCD 的定义
最大公约数（Greatest Common Divisor，GCD）指两个或多个整数共有约数中最大的一个。例如，12 和 18 的公约数是 1、2、3、6，其中最大的是 6，因此 gcd(12, 18) = 6。
2、GCD的符号
整数a和b的最大公约数是能同时整除a和b的最大整数，记为gcd(a,b)。负整数也可以算GCD，不过由于-a的因子和a的因子相同，在编码时只需要关注正整数的最大公约数。下面用C++函数std::_gcd(a,b)演示GCD的计算结果，GCD 的结果的符号通常与第一个参数的符号相同。
# include
// 包含C++标准库的头文件，通常用于竞赛编程，包含了几乎所有常用的库。
using namespace std;
// 使用标准命名空间，避免每次调用标准库函数时都要加std::前缀。
int main(){
// 主函数，程序的入口。
cout << __gcd(45,9) << "\n"; //9
// 计算45和9的最大公约数，输出9。
cout << __gcd(0,42) << "\n"; //42
// 计算0和42的最大公约数，输出42。
cout << __gcd(42,0) << "\n"; //42
// 计算42和0的最大公约数，输出42。
cout << __gcd(0,0) << "\n"; //0
// 计算0和0的最大公约数，输出0。
cout << __gcd(20,15) << "\n"; //5
// 计算20和15的最大公约数，输出5。
cout << __gcd(-20,15) << "\n"; //-5
// 计算-20和15的最大公约数，输出-5。
cout << __gcd(20,-15) << "\n"; //5
// 计算20和-15的最大公约数，输出5。
cout << __gcd(-20,-15) << "\n"; //-5
// 计算-20和-15的最大公约数，输出-5。
cout << __gcd((long long)98938441343232,(long long)33422) << "\n"; //2
// 计算98938441343232和33422的最大公约数，输出2。
}
3、GCD 的性质
交换律：gcd(a, b) = gcd(b, a)
结合律：gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
线性组合：gcd(a, b) 能整除任何形如 ax + by 的线性组合（x, y 为整数）
与倍数的关系：
若 a 整除 b，则 gcd(a, b) = |a|
gcd(ka, kb) = |k|·gcd(a, b)（k 为整数）
贝祖定理：存在整数 x 和 y，使得 ax + by = gcd(a, b)
余数性质：gcd(a, b) = gcd(b, a mod b)（欧几里得算法核心）
几个性质：(1) gcd(a,b)=gcd(a,a+b)=gcd(a,k·a+b)。
(2) gcd(ka,kb)=k·gcd(a,b)。
(3) 多个整数的最大公约数：gcd(a,b,c)=gcd(gcd(a,b),c)。
(4) 若gcd(a,b)=d，则gcd(a/d,b/d)=1，即a/d与b/d互素。这个定理很重要。
(5) gcd(a+cb,b)=gcd(a,b)。
3、欧几里得算法（辗转相除法）
算法思想
基于性质 6，反复用较大数除以较小数，用余数替换较大数，直到余数为 0。最后一个非零余数即为 GCD。
步骤：
若 b = 0，返回 a
否则，计算 a mod b，递归求解 gcd(b, a mod b)
数学证明：
若 d = gcd(a, b)，则 d 能整除 a 和 b，因此也能整除 a mod b = a - qb（q 为商）。同理，d 也是 b 和 a mod b 的公约数，故两数对的公约数集合相同，最大公约数相等。
时间复杂度
最优：O(1)（当其中一个数为 0 时）
最坏：O(log min(a, b))（每次取模至少减少一半）
5、C++ 实现
1. 递归实现
#include
#include
int gcd(int a, int b) {
if (b == 0)
return abs(a); // 处理负数情况
return gcd(b, a % b);
}
int main() {
std::cout << gcd(48, 18) << std::endl; // 输出 6
std::cout << gcd(-12, 15) << std::endl; // 输出 3
std::cout << gcd(0, 5) << std::endl; // 输出 5
std::cout << gcd(0, 0) << std::endl; // 输出 0（特殊处理）
return 0;
}
2. 迭代实现
#include
#include
int gcd_iter(int a, int b) {
a = abs(a);
b = abs(b);
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
int main() {
std::cout << gcd_iter(48, 18) << std::endl; // 输出 6
std::cout << gcd_iter(0, 5) << std::endl; // 输出 5
return 0;
}
关键点
处理负数：通过 abs 确保参数非负。
处理 0：gcd(0, 0) 通常返回 0，但数学上可能未定义，需根据需求处理。
6、扩展应用
多个数的 GCD：
递归计算 gcd(a, gcd(b, c))。
最小公倍数（LCM）：
利用公式 lcm(a, b) = |a·b| / gcd(a, b)。
扩展欧几里得算法：
求解贝祖系数（x, y）及线性方程 ax + by = gcd(a, b)。
7、总结
欧几里得算法是计算 GCD 的最高效方法。
实际应用中需注意处理负数、0 及大数问题。
GCD 是数论和密码学的基础，广泛应用于模运算、分数化简等场景。
二、最小公倍数（LCM）
1、LCM 的定义
最小公倍数（Least Common Multiple，LCM）指两个或多个整数共有倍数中最小的一个。例如，4 和 6 的倍数分别是 4, 8, 12, 16, ... 和 6, 12, 18, ...，它们的最小公倍数是 12，因此 lcm(4, 6) = 12。
2、LCM 的性质
交换律：lcm(a, b) = lcm(b, a)
结合律：lcm(a, lcm(b, c)) = lcm(lcm(a, b), c)
与 GCD 的关系：lcm(a, b) = |a·b| / gcd(a, b)
与倍数的关系：
若 a 整除 b，则 lcm(a, b) = |b|
lcm(ka, kb) = |k|·lcm(a, b)（k 为整数）
分配律：lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))
3、LCM 的计算方法
1. 基于 GCD 的计算
利用 LCM 与 GCD 的关系公式：
这是计算 LCM 的最常用方法。
2. 直接枚举法
从小到大枚举 a 和 b 的倍数，找到第一个共同的倍数。这种方法效率较低，仅适用于小整数。
4、C++ 实现
1. 基于 GCD 的实现
#include
#include
// 计算 GCD
int gcd(int a, int b) {
if (b == 0)
return abs(a);
return gcd(b, a % b);
}
// 计算 LCM
int lcm(int a, int b) {
if (a == 0 || b == 0)
return 0; // 特殊情况处理
return abs(a * b) / gcd(a, b);
}
int main() {
std::cout << lcm(4, 6) << std::endl; // 输出 12
std::cout << lcm(12, 18) << std::endl; // 输出 36
std::cout << lcm(0, 5) << std::endl; // 输出 0
std::cout << lcm(-4, 6) << std::endl; // 输出 12
return 0;
}
2. 直接枚举法实现
#include
#include
int lcm_enum(int a, int b) {
int max_num = std::max(a, b);
while (true) {
if (max_num % a == 0 && max_num % b == 0)
return max_num;
max_num++;
}
}
int main() {
std::cout << lcm_enum(4, 6) << std::endl; // 输出 12
std::cout << lcm_enum(12, 18) << std::endl; // 输出 36
return 0;
}
5、扩展应用
多个数的 LCM：
递归计算 lcm(a, lcm(b, c))。
分数运算：
在分数加减法中，LCM 用于通分。
周期性任务调度：
在计算任务周期时，LCM 可用于确定任务的最小重复周期。
6、总结
LCM 与 GCD 的关系是计算 LCM 的核心。
基于 GCD 的计算方法效率高，适用于大多数场景。
实际应用中需注意处理负数、0 及大数问题。
LCM 在数学、计算机科学和工程中有广泛应用。
7、示例问题
问题：计算 12、18 和 24 的最小公倍数。
解法：
计算 gcd(12, 18) = 6，lcm(12, 18) = (12 * 18) / 6 = 36。
计算 gcd(36, 24) = 12，lcm(36, 24) = (36 * 24) / 12 = 72。
最终结果为 72。
C++ 实现：
#include
#include
int gcd(int a, int b) {
if (b == 0)
return abs(a);
return gcd(b, a % b);
}
int lcm(int a, int b) {
if (a == 0 || b == 0)
return 0;
return abs(a * b) / gcd(a, b);
}
int lcm_multiple(int arr[], int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result = lcm(result, arr[i]);
}
return result;
}
int main() {
int arr[] = {12, 18, 24};
int n = sizeof(arr) / sizeof(arr[0]);
std::cout << lcm_multiple(arr, n) << std::endl; // 输出 72
return 0;
}