公约数和公倍数

什么是最大公约数

在信息学竞赛（OI）里，最大公约数（Greatest Common Divisor，简称 gcd）指的是两个或多个整数共有约数里最大的那个。例如，12 和 18 的公约数有 1、2、3、6，其中最大公约数是 6。在 C++ 里，计算两个数的最大公约数是一个常见操作，gcd 算法能够高效地算出两个整数的最大公约数。其功能不仅局限于单纯的数学计算，在很多算法和问题的求解中，最大公约数都扮演着关键角色。

辗转相除法

计算最大公约数最常用的算法是欧几里得算法（辗转相除法），其原理基于以下定理： 对于任意两个正整数 a 和 b（a > b），它们的最大公约数等于 b 和 a % b（a 除以 b 的余数）的最大公约数，即 gcd(a, b) = gcd(b, a % b)。

当 b 为 0 时，a 和 0 的最大公约数就是 a，这就是算法的终止条件。

代码实现

题面

给定两个正整数 a 和 b，求出它们的最大公约数。

输入输出样例

• 输入： 一行，包含两个正整数 a 和 b，用空格分隔。

示例输入：

12 18

• 输出： 输出一个整数，表示 a 和 b 的最大公约数。

示例输出：

6

代码实现

#include <iostream>
using namespace std;
 
// 欧几里得算法计算最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
 
int main() {
    int a, b;
    // 读入两个正整数
    cin >> a >> b;
    // 计算最大公约数
    int res = gcd(a, b);
    // 输出结果
    cout << res << endl;
    return 0;
}    

复杂度分析

时间复杂度

欧几里得算法的时间复杂度是 $O(\log(\min(a, b)))$。这是因为在每一次递归调用中，两个数中的较大数至少会减少一半。可以通过数学推导证明，在最坏情况下，每次递归后，问题规模会以指数级的速度缩小，所以总的递归次数是对数级别的。

空间复杂度

由于使用了递归实现，递归调用会使用系统栈空间，空间复杂度是 $O(\log(\min(a, b)))$，主要取决于递归的深度。

什么是最小公倍数

定义

一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。0 是任意一组整数的公倍数。

一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。

对整数 $a,b$，将其最小公倍数记为 $\operatorname{lcm}(a,b)$，不引起歧义时可简写为 $[a,b]$。

对整数 $a_1,\dots,a_n$，将其最小公倍数记为 $\operatorname{lcm}(a_1,\dots,a_n)$，不引起歧义时可简写为 $[a_1,\dots,a_n]$。

计算

设 $a = p_1^{k_{a_1}}p_2^{k_{a_2}} \cdots p_s^{k_{a_s}}$，$b = p_1^{k_{b_1}}p_2^{k_{b_2}} \cdots p_s^{k_{b_s}}$

我们发现，对于 $a$ 和 $b$ 的情况，二者的最大公约数等于

$p_1^{\min(k_{a_1}, k_{b_1})}p_2^{\min(k_{a_2}, k_{b_2})} \cdots p_s^{\min(k_{a_s}, k_{b_s})}$

最小公倍数等于

$p_1^{\max(k_{a_1}, k_{b_1})}p_2^{\max(k_{a_2}, k_{b_2})} \cdots p_s^{\max(k_{a_s}, k_{b_s})}$

由于 $k_a + k_b = \max(k_a, k_b) + \min(k_a, k_b)$

所以得到结论是 $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$

要求两个数的最小公倍数，先求出最大公约数即可。

例题