当前位置：首页 > news >正文

研究整除的性质——最大公约数（GCD）和最小公倍数（LCM）

news 来源：原创 2025/8/17 22:25:52

最大公约数（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 <bits/stdc++.h>
// 包含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 <iostream>
#include <cstdlib> // 用于 abs 函数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;  // 输出 6std::cout << gcd(-12, 15) << std::endl; // 输出 3std::cout << gcd(0, 5) << std::endl;    // 输出 5std::cout << gcd(0, 0) << std::endl;     // 输出 0（特殊处理）return 0;
}

2. 迭代实现

#include <iostream>
#include <cstdlib>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;  // 输出 6std::cout << gcd_iter(0, 5) << std::endl;    // 输出 5return 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 <iostream>
#include <cstdlib> // 用于 abs 函数// 计算 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;    // 输出 12std::cout << lcm(12, 18) << std::endl;  // 输出 36std::cout << lcm(0, 5) << std::endl;    // 输出 0std::cout << lcm(-4, 6) << std::endl;   // 输出 12return 0;
}

2. 直接枚举法实现

#include <iostream>
#include <algorithm> // 用于 max 函数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;   // 输出 12std::cout << lcm_enum(12, 18) << std::endl; // 输出 36return 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 <iostream>
#include <cstdlib>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; // 输出 72return 0;
}