整数与整除

前言

12 和 18 有什么共同点？它们都能被 6 整除——6 是它们的最大公约数（GCD）。它们又都是 36 的因数——36 是它们的最小公倍数（LCM）。

这些看似简单的事实，在算法竞赛中无处不在。当你需要把一个分数化简、判断两个周期会不会同步、或者解模方程时，GCD 和 LCM 就是你的起点。而更深层的扩展欧几里得算法，不仅能算 GCD，还能帮你解方程 $ax + by = \gcd(a,b)$——这是整个模运算体系的基石。

问题的本质

整除

如果 $a$ 除以 $b$ 余数为 0（即 $a = kb$），我们说 $b$ 整除 $a$，记作 $b \mid a$。

整除有一个重要性质：如果 $d \mid a$ 且 $d \mid b$，那么 $d \mid (a + b)$ 和 $d \mid (a - b)$。 这个性质是欧几里得算法的理论基础。

GCD 和 LCM

$\gcd(a, b)$：能同时整除 $a$ 和 $b$ 的最大正整数。

$\text{lcm}(a, b)$：同时是 $a$ 和 $b$ 的倍数的最小正整数。

它们之间的关系：$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$。

所以算 LCM 只需要先算 GCD：$\text{lcm}(a, b) = a / \gcd(a,b) \times b$（先除后乘防溢出）。

理论 + 代码

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

$\gcd(a, b) = \gcd(b, a \bmod b)$。当 $b = 0$ 时，$\gcd(a, 0) = a$。特殊地，$\gcd(0, 0) = 0$。

为什么这是对的？ 更一般地，$\gcd(a - kb, b) = \gcd(a, b)$ 对任意整数 $k$ 成立。原因很简单：任何能同时整除 $a$ 和 $b$ 的数 $d$，也能整除 $a - kb$（因为 $d \mid a$ 且 $d \mid kb$，所以 $d \mid (a - kb)$）。反过来也对。所以 $\{a, b\}$ 的公约数集合 $= \{a-kb, b\}$ 的公约数集合，GCD 自然不变。

取 $k = \lfloor a/b \rfloor$，就得到 $\gcd(a, b) = \gcd(b, a \bmod b)$。

走一遍过程：$\gcd(48, 18)$。

步骤	a	b	a mod b
1	48	18	12
2	18	12	6
3	12	6	0
4	6	0	—（b=0，答案是 6）

4 步就得到 $\gcd(48, 18) = 6$。

它有多快？ 每次取余至少让较大的数减半（因为 $a \bmod b \le a/2$），所以两个数每两步就各缩小一半。总步数 $O(\log \min(a, b))$——即使 $a, b$ 高达 $10^{18}$，也只需约 60 步。最坏情况发生在 Fibonacci 数列上（比如 $\gcd(F_n, F_{n-1})$ 需要 $n$ 步），但 Fibonacci 数增长极快，所以实际不会太慢。

long long gcd(long long a, long long b) {
    while (b) {
        long long t = b;
        b = a % b;    // ① 取余数
        a = t;         // ② 原来的 b 变成新的 a
    }
    return a;          // ③ b 为 0 时，a 就是 GCD
}

C++17 可以直接用 std::gcd(a, b)，需要 #include <numeric>。

扩展欧几里得算法

不仅能算 $\gcd(a, b)$，还能找到整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

这就是贝祖定理：对任意整数 $a, b$，存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1; y = 0;     // ① 边界：gcd(a,0) = a，a×1 + 0×0 = a
        return a;
    }
    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);  // ② 递归
    x = y1;                 // ③ 回代
    y = x1 - (a / b) * y1;  // ④ 关键公式
    return g;
}

走一遍过程：求 $48x + 18y = 6$。

1. exgcd(48, 18) → 递归 exgcd(18, 12)
2. exgcd(18, 12) → 递归 exgcd(12, 6)
3. exgcd(12, 6) → 递归 exgcd(6, 0)
4. exgcd(6, 0) → $x_0 = 1, y_0 = 0$，返回 6
5. 回代到步骤 3：$x_1 = y_0 = 0$，$y_1 = x_0 - 12/6 \times y_0 = 1 - 2 \times 0 = 1$。所以 $12 \times 0 + 6 \times 1 = 6$。✓
6. 回代到步骤 2：$x_2 = y_1 = 1$，$y_2 = x_1 - 18/12 \times y_1 = 0 - 1 \times 1 = -1$。所以 $18 \times 1 + 12 \times (-1) = 6$。✓
7. 回代到步骤 1：$x_3 = y_2 = -1$，$y_3 = x_2 - 48/18 \times y_2 = 1 - 2 \times (-1) = 3$。所以 $48 \times (-1) + 18 \times 3 = -48 + 54 = 6$。✓

答案是 $x = -1, y = 3$：$48 \times (-1) + 18 \times 3 = 6$。

④ 为什么这样回代？ 递归调用得到 $bx_1 + (a \bmod b)y_1 = g$。而 $a \bmod b = a - \lfloor a/b \rfloor \cdot b$，代入得 $bx_1 + (a - \lfloor a/b \rfloor \cdot b)y_1 = g$，整理得 $ay_1 + b(x_1 - \lfloor a/b \rfloor \cdot y_1) = g$。所以 $x = y_1$，$y = x_1 - \lfloor a/b \rfloor \cdot y_1$。

例题

例题 1：M&A 015 — Calculate GCD（★1）

题目：给定两个正整数 $A, B$，求 $\gcd(A, B)$。

数据范围：$1 \le A, B \le 10^{18}$

—— AtCoder M&A 015

思路：直接用欧几里得算法（辗转相除法）。$A, B \le 10^{18}$，要用 long long。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {                // ① b 不为 0 时继续
        long long t = b;
        b = a % b;             // ② 取余
        a = t;                 // ③ 交换
    }
    return a;
}

int main() {
    long long A, B;
    scanf("%lld%lld", &A, &B);
    printf("%lld\n", gcd(A, B));
}

逐行解析：

• ①②③ 欧几里得算法的核心：$\gcd(a, b) = \gcd(b, a \bmod b)$。每一步 $b$ 至少减半，所以循环次数 $O(\log \min(a, b))$。

---

例题 2：M&A 016 — Greatest Common Divisor of N Integers（★2）

题目：给定 $N$ 个正整数 $A_1, A_2, \ldots, A_N$，求它们的最大公约数。

数据范围：$2 \le N \le 1000$，$1 \le A_i \le 10^{18}$

—— AtCoder M&A 016

思路：$\gcd(A_1, A_2, \ldots, A_N) = \gcd(\gcd(A_1, A_2), A_3, \ldots, A_N)$。从左到右依次求 GCD。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    int N;
    scanf("%d", &N);
    long long g = 0;    // ① gcd(0, x) = x
    for (int i = 0; i < N; i++) {
        long long a;
        scanf("%lld", &a);
        g = gcd(g, a);  // ② 依次合并
    }
    printf("%lld\n", g);
}

逐行解析：

• ① 初始值 g = 0。因为 $\gcd(0, x) = x$（0 能被任何数整除），所以第一次 gcd(0, A[0]) = A[0]。
• ② 每读入一个数就和当前的 GCD 合并。

---

例题 3：M&A 017 — Least Common Multiple of N Integers（★2）

题目：给定 $N$ 个正整数，求它们的最小公倍数。

数据范围：$2 \le N \le 1000$，$1 \le A_i \le 10^{18}$

—— AtCoder M&A 017

思路：$\text{lcm}(a, b) = a / \gcd(a, b) \times b$。先除后乘防溢出。同样从左到右依次合并。

代码：

#include <cstdio>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

int main() {
    int N;
    scanf("%d", &N);
    long long l = 1;    // ① 初始值 1
    for (int i = 0; i < N; i++) {
        long long a;
        scanf("%lld", &a);
        l = l / gcd(l, a) * a;  // ② 先除后乘！
    }
    printf("%lld\n", l);
}

逐行解析：

• ② l / gcd(l, a) * a：先除 $\gcd$ 再乘 $a$。如果写成 l * a / gcd(l, a)，中间值可能溢出 long long。

---

例题 4：M&A 072 — Max GCD 2（★3）

题目：给定两个整数 $A, B$（$A \le B$），在 $A$ 到 $B$ 之间选两个不同的整数，使 GCD 最大。输出最大 GCD。

数据范围：$1 \le A < B \le 2 \times 10^5$

—— AtCoder M&A 072

思路：如果最大 GCD 是 $g$，那么区间 $[A, B]$ 中至少有两个 $g$ 的倍数。最大的 $g$ 满足 $\lfloor B/g \rfloor - \lfloor (A-1)/g \rfloor \ge 2$，即 $B/g - (A-1)/g \ge 2$，等价于 $g \le B - A$（当 $B - A \ge g$ 时，$A + g$ 和某个 $g$ 的倍数都在 $[A, B]$ 中）。

所以答案就是 $B - A$ 当 $B > A$ 时？不对。更准确的：答案就是满足 $2g \le B$ 且区间中至少有两个 $g$ 的倍数的最大 $g$。

简单做法：从 $B - A$ 倒着找第一个满足条件的 $g$。

代码：

#include <cstdio>
using namespace std;

int main() {
    int A, B;
    scanf("%d%d", &A, &B);

    int ans = 1;
    for (int g = B - A; g >= 1; g--) {  // ① 从大到小枚举 g
        // ② 检查 [A, B] 中是否有至少两个 g 的倍数
        int cnt = B / g - (A - 1) / g;  // [A,B] 中 g 的倍数个数
        if (cnt >= 2) {
            ans = g;
            break;
        }
    }
    printf("%d\n", ans);
}

逐行解析：

• ① 从 $B - A$ 开始往小枚举。因为如果 $g > B - A$，则 $[A, B]$ 中最多只有一个 $g$ 的倍数（相邻 $g$ 的倍数间距为 $g > B - A$）。
• ② B / g - (A - 1) / g 是经典的区间中倍数个数的公式。

---

例题 5：M&A 013 — Divisor Enumeration（★1）

题目：给定整数 $N$，枚举 $N$ 的所有约数。

数据范围：$1 \le N \le 10^{13}$

—— AtCoder M&A 013

思路：从 1 到 $\sqrt{N}$ 试除，每找到一个约数 $i$ 就同时得到 $N/i$。这道题在 00-02 排序 中已经用排序输出做过。这里强调整除性的角度。

代码（与 00-02 相同）：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    vector<long long> divs;
    for (long long i = 1; i * i <= N; i++) {
        if (N % i == 0) {
            divs.push_back(i);
            if (i != N / i)
                divs.push_back(N / i);
        }
    }
    sort(divs.begin(), divs.end());
    for (auto d : divs)
        printf("%lld\n", d);
}

参考文献

理论讲义 — AtCoder Algorithm Lectures

• Euclid の互除法（難易度 2）

教材讲解 — 競技プログラミングの鉄則 第 5 章

• 5.2 B27 Calculate LCM（GCD/LCM 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 015 Calculate GCD（GCD基础）【例题】
• 016 Greatest Common Divisor of N Integers【例题】
• 017 Least Common Multiple of N Integers【例题】
• 072 Max GCD 2（区间最大GCD）【例题】
• 013 Divisor Enumeration（约数枚举）【例题】
• 014 Factorization（素因数分解）
• 042 Sum of Divisors（约数函数求和）
• 093 Large LCM（★3，LCM溢出判断）

系统练习 — 競技プログラミングの鉄則

• A27 Calculate GCD（同M&A 015）
• A28 Blackboard（N个数的GCD和LCM）
• A31 Divisors（约数个数）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化