算法刷题系列（四）：数学问题中的整除、最大公约数与模运算
算法刷题系列（四）：数学问题中的整除、最大公约数与模运算
数学题常常不需要复杂的数据结构，关键是找到一个能缩小问题的性质：两个数是否有共同因子、一个余数如何随运算变化、计数结果是否会超过整数范围。
本篇承接“算法刷题系列路线图”中的基础工具阶段，围绕整除、最大公约数和模运算介绍几种常用的建模方法。例子和代码均为原创，分别提供 Java 与 Python 实现。
一、先把题目中的数学关系写出来
读到“整除”“周期”“最简比例”“循环计数”这类描述时，先不要急着写循环。可以先把它翻译成等式或条件：
a能被b整除：存在整数k，使a = b × k。a与b的最大公约数：同时整除二者的最大正整数。x除以m的余数：用x mod m表示，结果用于描述周期或同余关系。
数学建模的作用，是把题目里可能很大的数或重复过程，转成更小的因子、余数或状态。
二、最大公约数：把共同因子问题缩小
给定两个正整数 a 和 b，最大公约数记为 gcd(a, b)。最直接的方法是从较小的数开始向下试除，但最坏需要检查许多候选值。
欧几里得算法使用下面这个性质：
1
gcd(a, b) = gcd(b, a mod b)
为什么可以这样替换？若 a = q × b + r，那么任何同时整除 a 和 b 的数，也会整除 r = a - q × b；反过来，同时整除 b 和 r 的数也会整除 a。因此两组数的公约数集合相同。
重复替换，直到余数为零。此时另一个数就是最大公约数。
手动推演
计算 gcd(84, 30)：
1
2
3
4
5
6
gcd(84, 30)
= gcd(30, 84 mod 30)
= gcd(30, 24)
= gcd(24, 6)
= gcd(6, 0)
= 6
每一步都把第二个数变成更小的余数，因此算法会很快结束，时间复杂度为 O(log(min(a, b)))。
三、Java：实现 GCD 和最小公倍数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class NumberTheory {
// This version accepts non-negative inputs.
public static long gcd(long a, long b) {
if (a < 0 || b < 0) {
throw new IllegalArgumentException("Inputs must be non-negative");
}
while (b != 0) {
long remainder = a % b;
a = b;
b = remainder;
}
return a;
}
public static long lcm(long a, long b) {
if (a < 0 || b < 0) {
throw new IllegalArgumentException("Inputs must be non-negative");
}
if (a == 0 || b == 0) {
return 0;
}
return Math.multiplyExact(a / gcd(a, b), b);
}
}
最小公倍数满足：
1
lcm(a, b) = a / gcd(a, b) × b
先除再乘比直接计算 a × b / gcd(a, b) 更稳妥，因为中间乘积较小。不过结果本身仍可能超过 long 的范围，所以示例使用 Math.multiplyExact：溢出时显式抛出异常，而不是返回错误数值。
本实现约定输入为非负数。若题目允许负数，应按题意明确 GCD/LCM 的符号约定，并处理 Long.MIN_VALUE 取绝对值无法用 long 表示的边界。
四、Python：同一算法，整数范围不同
1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a: int, b: int) -> int:
a = abs(a)
b = abs(b)
while b:
a, b = b, a % b
return a
def lcm(a: int, b: int) -> int:
if a == 0 or b == 0:
return 0
return abs(a // gcd(a, b) * b)
Python 整数可以自动扩展精度，因此不会像固定宽度的 long 那样发生常规整数溢出；但数值越大，占用的时间和内存仍然越多。
五、应用一：把比例约成最简形式
假设一份饮料由 84 份果汁和 30 份水组成，想写成最简整数比例。两项都除以最大公约数：
1
2
gcd(84, 30) = 6
84 : 30 = 14 : 5
这类题的结构是：多个量按相同比例缩放，要求找到最小整数表示。最大公约数可以去掉所有共同因子。
如果比例中存在零或负数，应根据题意定义结果形式；不能在未确认约束前直接套用正整数示例。
六、模运算：关注余数而不是完整数值
a mod m 表示 a 除以正整数 m 的余数。模运算常见于：
- 计算周期性状态，例如指针循环移动；
- 只需要计数结果对某个数取余；
- 判断两个整数是否同余；
- 避免中间结果增长得过大。
对于整数 a、b 和正整数 m，有：
1
2
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
如果题目要求答案对 m 取余，可以在每次更新后取余，而不是等到最后再处理一个巨大中间值。
Java：避免加法先溢出
1
2
3
4
5
6
7
8
static long addMod(long a, long b, long mod) {
if (mod <= 0 || a < 0 || b < 0 || a >= mod || b >= mod) {
throw new IllegalArgumentException("Expected 0 <= a, b < mod");
}
// Preconditions keep a + b below Long.MAX_VALUE.
return (a + b) % mod;
}
这里的前置条件保证 a、b 都已经处于 [0, mod)。实际使用时，还必须确认 2 × (mod - 1) 不会超过 long 上限；如果模数很大，简单的加法仍可能溢出，需要使用更安全的加法策略或更宽的整数类型。
对于常见的 1_000_000_007 模数，两个规范化余数相加不会超过 long 范围。若进一步做乘法，也应根据模数和语言整数宽度检查乘积是否会溢出。
Python：每步规范化余数
1
2
3
4
def add_mod(a: int, b: int, mod: int) -> int:
if mod <= 0:
raise ValueError("mod must be positive")
return (a + b) % mod
Python 的 % 对正模数返回非负余数。因此即使 a 或 b 为负数，结果仍会规范到 [0, mod)。Java 对负数 % 的行为不同；若 Java 代码需要处理负值并要求非负结果，可使用 Math.floorMod(value, mod)。
七、边界与测试
GCD 中出现零
1
2
gcd(0, 30) = 30
gcd(0, 0) = 0
欧几里得算法本身可以处理这些情况。LCM 的代码也单独处理了零，因为任意整数与零的最小公倍数按常见约定为零。
两个数互质
若 gcd(a, b) = 1，说明二者没有大于 1 的共同因子。互质不要求两个数本身是质数，例如 8 和 15 互质。
模数必须为正
周期和同余问题通常要求模数 m > 0。模数为零时取余没有定义，因此实现应拒绝该输入。
结果可能比输入更大
最小公倍数可能大于 a 和 b，固定宽度整数还可能无法表示结果。复杂度分析之外也要检查数值范围。
八、常见误区
- 把互质误认为都是质数：互质是两个数之间的关系。
- 不检查零和负数约束：GCD、LCM 和取模的边界行为要按题意处理。
- 以为“先除再乘”能完全消除溢出：它能降低中间值，但最终结果仍可能超范围。
- Java 和 Python 的负数取模结果默认相同：不同语言的余数规则可能不同。
- 不说明模数范围就直接做乘法：
(a % m) * (b % m)仍可能在固定宽度类型中溢出。 - 看到数学标签就开始枚举：先找整除、周期、对称、单调或不变量关系，可能直接减少搜索量。
九、与后续主题的连接
最大公约数展示了如何用不变量把数值问题逐步缩小；模运算则把周期性状态规范到有限范围。这些思路会在后续内容中反复出现：
- 排序与二分利用顺序或单调性缩小搜索空间；
- 位运算用有限个二进制位表示状态；
- 二进制枚举和状压 DP 用掩码表示集合；
- 矩阵快速幂用模运算控制递推结果的范围。
下一篇将从数值关系转向二进制表示，讨论位运算如何直接操作一个整数中的状态位。
小结
数学题的第一步通常是把自然语言条件写成等式、整除关系或余数关系。欧几里得算法用 gcd(a, b) = gcd(b, a mod b) 快速求最大公约数；模运算则用余数描述周期并控制结果范围。实现时还要显式检查零、负数、模数和整数溢出的约束。