一、gcd

1.引入

一组整数的公约数，是指同时是这组数中每一个数的约数的数。

显然，±1是任意一组整数的公约数。

最大公约数（也称最大公因数，英文全称为 Greatest Common Divisor，常缩写为 gcd）。一组整数的最大公约数，是指所有公约数里面最大的一个。对不全为 0的整数 𝑎,𝑏，将其最大公约数记为 gcd(𝑎, 𝑏)。对不全为 0的整数$a_1$, …… ,$a_n$，将其最大公约数记为 gcd($a_1$, …… ,$a_n$)，在无争议的情况下，a和b最大公因数可表示为(a, b)。

特别的，任意一个不为零整数和0的最大公约数都是这个数的绝对值，并且gcd(0, 0)没有意义。

2.gcd的几种实现方法

2.1 穷举法

对于初学者而言，永远存在着暴力枚举法解决任何问题，下面是实现代码及注释：

int gcd(int a, int b) {
    // 处理特殊情况：0和任何数的GCD是另一个数的绝对值
    if (a == 0) return b < 0 ? -b : b;
    if (b == 0) return a < 0 ? -a : a;
    
    // 取绝对值，因为我们只关心正公约数
    a = a < 0 ? -a : a;
    b = b < 0 ? -b : b;
    
    // 找到较小的数作为枚举上限
    int limit = (a < b) ? a : b;
    int gcd = 1;  // 1总是公约数
    
    // 从1到limit枚举所有可能的公约数
    for (int i = 1; i <= limit; ++i) {
        // 检查i是否能同时整除a和b
        if (a % i == 0 && b % i == 0) {
            gcd = i;  // 更新找到的公约数
        }
    }
    
    return gcd;
}

我们不难发现此方法的时间复杂度取决于a，b中较小的数，即O(min(|a|, |b|))，为线性时间复杂度，显然不是最优解。

2.2 素因数分解法

核心思想：分别将两个数分解为质因数的乘积，然后取共有质因数的最小指数幂的乘积。

数学公式：如果$a = p₁^{(e₁)} p₂^{(e₂)} … pₖ^{(eₖ)},b = p₁^{(f₁)} p₂^{(f₂)} … pₖ^{(fₖ)}$

则$gcd(a, b) = p₁^{(min(e₁, f₁))} p₂^{(min(e₂, f₂))} … pₖ^{(min(eₖ, fₖ))}$

基本变量

• a, b：两个要求最大公约数的正整数
• p₁, p₂, …, pₖ：质因数（素数）
  • 所有质数按从小到大的顺序排列
  • 这些是a和b分解后所有出现的质因数的集合

指数变量

• e₁, e₂, …, eₖ：a的质因数指数
  • e₁是a中质因数p₁出现的次数（指数）
  • e₂是a中质因数p₂出现的次数
  • …依此类推
  • 如果某个质因数不在a中，则对应的eᵢ = 0
• f₁, f₂, …, fₖ：b的质因数指数
  • f₁是b中质因数p₁出现的次数
  • f₂是b中质因数p₂出现的次数
  • …依此类推

数学原理

一个数要同时整除a和b，它的每个质因数的指数不能超过a和b中该质因数指数的较小值。

取最小指数的原因

• 对于质因数pᵢ：
  • 如果它在gcd中的指数>min(eᵢ, fᵢ)，那么：
    • 要么不能整除a（如果指数>eᵢ）
    • 要么不能整除b（如果指数>fᵢ）
  • 所以要保证整除，指数必须≤min(eᵢ, fᵢ)
  • 为了gcd最大，我们取等号：指数=min(eᵢ, fᵢ)

例子验证

a = 12 = 2² × 3¹
b = 18 = 2¹ × 3²

gcd(12, 18) = ?
对质因数2：min(2, 1) = 1 → 2¹
对质因数3：min(1, 2) = 1 → 3¹
gcd = 2¹ × 3¹ = 6 ✓

结合下面带有详细注释的代码可以理解：

// 素因数分解法求最大公约数（GCD）
int gcd(int a, int b) {
    // 处理特殊情况和负数
    if (a == 0) return abs(b);  // gcd(0,b)=|b|
    if (b == 0) return abs(a);  // gcd(a,0)=|a|
    
    a = abs(a);  // 转为正数
    b = abs(b);
    
    if (a == b) return a;       // 相等数快速返回
    if (a == 1 || b == 1) return 1;  // 包含1的情况
    
    int gcd = 1;  // 初始化为1（最小公约数）
    
    // 第一阶段：提取所有公共的因子2
    // 2是唯一的偶质数，单独处理可优化性能
    while (a % 2 == 0 && b % 2 == 0) {
        gcd *= 2;
        a /= 2;
        b /= 2;
    }
    
    // 第二阶段：检查奇数因子
    // 只需检查到min(a,b)的平方根，因为大于平方根的因子最多只有一个
    for (int i = 3; i * i <= min(a, b); i += 2) {
        // 提取所有公共的因子i
        while (a % i == 0 && b % i == 0) {
            gcd *= i;
            a /= i;
            b /= i;
        }
    }
    
    // 第三阶段：处理大于平方根的公共质因数
    if (a == b && a > 1) {
        gcd *= a;  // 这是剩余的唯一公共质因数
    }
    
    return gcd;
}

/*
算法思想：
1. 分别分解两个数的质因数
2. 取所有公共质因数的最小次幂乘积
3. 优化：单独处理因子2，只检查奇数，减少循环次数

空间复杂度：O(1)

示例：
gcd(36,48) = 12
36 = 2²×3²
48 = 2⁴×3
公共质因数：2²×3 = 12
*/

此时时间复杂度为O$(\sqrt{min(a,b)})$，相较穷举法有所提升，但在大数处理上依然不优秀。

对于以上质数（素数）的处理我会在后面的篇章中单独详解，敬请期待。

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

前面的两种方法是为了帮助你更好的理解gcd，论算法竞赛中最常用的求gcd的方法还得是大名鼎鼎的欧几里得算法。

现在我们抛开刚才的两种方法重新思考，如果我们已经知道两个数a和b，怎么求gcd(a, b)呢？

我们不妨设a > b，我们不难发现，如果b是a的一个约数，那么gcd(a, b) = b。

下面我们分析其他情况即a不能被b整除的情况：

证明

给定整数 $a$ 和 $b$（$b>0$，b>0），令 $k$ 为 $a$ 除以 $b$ 的商，$c$ 为余数，即：

$a=bk+c,0≤c<b,$显然，c = a % b。

现在证明：若 $d$ 是 $a$ 和 $b$ 的公约数，则 $d$ 也是 $b$ 和 $c$ 的公约数

不妨设d整除a且d整除b，由 $c=a-bk$ 得：$\frac{c}{d} = \frac{a}{d} – \frac{b}{d}k$

因为 $\frac{a}{d}$ 和 $\frac{b}{d}$ 均为整数，则 $\frac{c}{d}$ 也一定为整数，即d整除c，因此d是b和c的公约数。

现在证明：若 $d$ 是 $b$ 和 $c$ 的公约数，则 $d$ 也是 $a$ 和 $b$ 的公约数

不妨设d整除b且d整除c，由 $a = bk + c$ 得：$\frac{a}{d} = \frac{b}{d}k + \frac{c}{d}$

因为 $\frac{b}{d}$ 和 $\frac{c}{d}$ 均为整数，则 $\frac{a}{d}$ 也一定为整数，即d整除a，因此d是a和b的公约数。

综上，结论为a和b的公约数集合与b和a%b的公约数集合完全相同。

经过以上一系列的数学推理，我们得到结论

$gcd(a,b) = gcd(b,a\,\,mod\,\,b)$

有了以上结论，我们可以写出gcd的递归欧几里得的三目运算代码，只需一行：

int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}

显然，我们也可以写出迭代欧几里得如下：

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

这两者的时间复杂度都已经达到最优解之一，即O$(1.44*log_2(min(a,b))$。

算法竞赛中更推荐使用递归欧几里得三目运算代码，它更加简洁，同时对于C++17及以上（普遍的竞赛环境），STL库中的gcd使用的是递归欧几里得算法，所以时间复杂度也是最优之一，可以在万能头下直接调用gcd(a, b)返回的值就是最大公约数，单独对应的头文件是#include<numeric>。

同时对于欧几里得算法还有两个比较常见的应用代码如下，可以了解：

 int gcd (int a, int b) {
    if (b == 0) return a;  // 处理b为0的情况
    
    while (true) {
        a %= b;
        if (a == 0) break;
        
        b %= a;
        if (b == 0) {
            // 交换，使gcd在a中
            a ^= b;
            b ^= a;
            a ^= b;
            break;
        }
    }
    return a;  // 或者 return a + b，因为此时b=0
}


//下面的代码使用的是改进欧几里得算法
int gcd(int a, int b) {    
    if(b) while((a%=b) && (b%=a));  // 双向取模，利用短路    
    return a+b;  // 结束时必有一个为0，和即为gcd
}

二、lcm

1.引入

最小公倍数（英文缩写为lcm），就是指对于2个数a和b，它们的公倍数中最小的那个，拿100和75举例，它们的公倍数有300 600 900...，其中最小的是300，所以100和75的最小公倍数为300，a和b的最小公倍数在无争议的情况下可以表示为[a, b]。

2.lcm的实现方式

当你熟练掌握gcd后，lcm就会显得异常的简单，因为对于两个整数a，b而言，

$a*b = lcm(a,b)*gcd(a,b)$

因此lcm代码就可以在有gcd函数之后直接使用，函数如下：

int lcm(int a, int b) {
	return a / gcd(a, b) * b; //防止溢出
	// gcd(int a,int b) 必需被定义或声明过
}

或者也可以使用#include<numeric>或者万能头后调用STL库中的lcm，和上面gcd相同，也是极快的解的一种，比如整数a和b的最小公倍数值就为lcm(a, b)。

三、裴蜀定理

1.引入

裴蜀定理（Bézout’s lemma）是数论中的一个重要定理，表明对于任意两个整数 $a$ 和 $b$，存在整数 $x$ 和 $y$，使得 $ax+by=\gcd (a,b)$。

推论：整数a和b互素，当且仅当当前存在整数x与y使得ax+by=1。

具体例题待我有时间发掘……

ok，以上就是gcd和lcm所有的基础内容了，希望大家都能好好掌握，以后对于进阶欧几里得算法和其他相关进阶算法我想结合着具体题目来解决讲解。无论如何，知识常看常新，下篇文章见喽。

四、经典例题

P1072 [NOIP 2009 提高组] Hankson 的趣味题 – 洛谷