1. 概述
处理大数运算时，中间结果很容易超出数据类型限制。模运算（Modular Arithmetic）正是解决这类问题的利器，能有效控制数值范围防止溢出。本文将以模 (10^9 + 7) 为例，系统讲解模运算的实战技巧。
2. 基础原理
掌握模运算前，先快速回顾几个核心概念——这些是高效实现模运算的基石。
2.1 对称模与非负余数
计算 (a \mod b) 时，根据除法算法可得到非负余数 (r)：
a = q·b + r
其中 b>0 且 r≥0
⚠️ 注意：本文默认模数 (b) 为正数
稍作变形即可得到负余数形式：
a = (q+1)b - (b - r)
其中 -(b-r)≤0
数学上这称为对称模（Symmetric Modulo），余数范围在 ([-b, b))。但大多数编程语言实现时，对于正模数会返回 ([0, b)) 范围内的非负余数。
2.2 同余性质
模运算中有个关键特性——同余关系（Congruence）：
(a mod n) = (b mod n) ⇔ a≡b (mod n)
核心结论：两数 (a) 和 (b) 除以 (n) 余数相同时，称其模 (n) 同余。例如 (10 ≡ 4 \pmod{3})。
2.3 模运算策略
结合对称模和同余性质，我们制定高效策略：优先选择绝对值更小的中间结果。定义两个辅助方法：
static int minSymmetricMod(int x) {
if (Math.abs(x % MOD) <= Math.abs((MOD - x) % MOD)) {
return x % MOD;
} else {
return -1 * ((MOD - x) % MOD);
}
}
static int mod(int x) {
if (x >= 0) {
return x % MOD;
} else {
return mod(MOD + x);
}
}
✅ 实现要点：
minSymmetricMod()返回绝对值更小的余数mod()保证返回非负结果- 通过方法重载支持
long类型- 本文使用 (MOD = 10^9 + 7)，但原理通用
3. 模加法
3.1 分配律特性
模运算对加法满足分配律：
(a + b) mod n = ((a mod n) + (b mod n)) mod n
优化策略：中间结果采用对称模：
(a + b) mod n = ((a symmetric_mod n) + (b symmetric_mod n)) mod n
关键优势：内层
symmetric_mod缩小数值范围，外层mod确保结果非负。
3.2 实现代码
static int modSum(int a, int b) {
return mod(minSymmetricMod(a) + minSymmetricMod(b));
}
验证测试用例：
assertEquals(1000000006, modSum(500000003, 500000003));
assertEquals(1, modSum(1000000006, 2));
assertEquals(999999999, modSum(999999999, 0));
assertEquals(1000000005, modSum(1000000006, 1000000006));
4. 模减法
4.1 分配律特性
模运算对减法同样满足分配律：
(a - b) mod n = ((a mod n) - (b mod n)) mod n
优化策略：中间结果使用对称模：
(a - b) mod n = ((a symmetric_mod n) - (b symmetric_mod n)) mod n
4.2 实现代码
static int modSubtract(int a, int b) {
return mod(minSymmetricMod(a) - minSymmetricMod(b));
}
⚠️ 踩坑提示：
minSymmetricMod()确保中间项绝对值最小化，避免溢出风险。
测试用例验证：
assertEquals(0, modSubtract(500000003, 500000003));
assertEquals(1000000005, modSubtract(1, 3));
assertEquals(999999999, modSubtract(999999999, 0));
5. 模乘法
5.1 分配律特性
模运算对乘法满足分配律：
(a * b) mod n = ((a mod n) * (b mod n)) mod n
优化策略：中间结果采用对称模：
(a * b) mod n = ((a symmetric_mod n) * (b symmetric_mod n)) mod n
5.2 实现代码
static long modMultiply(int a, int b) {
int result = minSymmetricMod((long) minSymmetricMod(a) * (long) minSymmetricMod(b));
return mod(result);
}
❌ 关键警告：
minSymmetricMod()返回值最大为 (MOD-1)- 但乘法结果可能超
Integer.MAX_VALUE- 必须用
long类型强制转换！
测试用例验证：
assertEquals(1, modMultiply(1000000006, 1000000006));
assertEquals(0, modMultiply(999999999, 0));
assertEquals(1000000006, modMultiply(500000003, 2));
assertEquals(250000002, modMultiply(500000003, 500000003));
6. 模幂运算
6.1 模幂特性
模运算对乘法满足分配律，因此可简化模幂运算：
(a ^ b) mod n = ((a mod n) ^ b) mod n
⚠️ 重要区别：模运算对幂运算不满足分配律（指数 (b) 不取模）！
优化策略：底数采用对称模：
(a ^ b) mod n = ((a symmetric_mod n) ^ b) mod n
6.2 实现代码
static int modPower(int base, int exp) {
int result = 1;
int b = base;
while (exp > 0) {
if ((exp & 1) == 1) {
result = minSymmetricMod((long) minSymmetricMod(result) * (long) minSymmetricMod(b));
}
b = minSymmetricMod((long) minSymmetricMod(b) * (long) minSymmetricMod(b));
exp >>= 1;
}
return mod(result);
}
✅ 实现亮点：
- 采用快速幂算法提升效率
- 所有中间值用
minSymmetricMod()处理- 乘法强制转为
long防溢出
测试用例验证：
assertEquals(16, modPower(2, 4));
assertEquals(1, modPower(2, 0));
assertEquals(1000000006, modPower(1000000006, 1));
assertEquals(1000000006, modPower(500000003, 500000003));
assertEquals(500000004, modPower(500000004, 500000004));
assertEquals(250000004, modPower(500000005, 500000005));
7. 模乘法逆元
核心前提：模乘法逆元存在当且仅当 (a) 与模数 (m) 互质。本文 (m=10^9+7) 是质数，与所有数互质。
7.1 贝祖等式
根据贝祖等式，存在系数 (x, y) 满足：
gcd(a, b) = x·a + y·b
当 (a, b) 互质时：
x·a + y·b = 1
两边取模 (b)：
(x·a) % b = 1
关键结论：这正是模乘法逆元的定义 ((a^{-1} \cdot a) % b = 1)。问题转化为求贝祖系数 (x)。
7.2 扩展欧几里得实现
static int[] extendedGcd(int a, int b) {
if (b == 0) {
return new int[] { a, 1, 0 };
}
int[] result = extendedGcd(b, a % b);
int gcd = result[0];
int x = result[2];
int y = result[1] - (a / b) * result[2];
return new int[] { gcd, x, y };
}
求逆元方法：
static int modInverse(int a) {
int[] result = extendedGcd(a, MOD);
int x = result[1];
return mod(x);
}
测试用例验证：
assertEquals(500000004, modInverse(2));
assertEquals(1, modInverse(1));
assertEquals(1000000006, modInverse(1000000006));
assertEquals(1000000005, modInverse(500000003));
8. 模除法
前提条件：仅当除数与模数互质时（本文恒成立）才能进行模除法。
static int modDivide(int a, int b) {
return mod(modMultiply(a, modInverse(b)));
}
本质：模除法 = 被除数 × 除数的模乘法逆元
测试用例验证：
assertEquals(500000004, modDivide(1, 2));
assertEquals(2, modDivide(4, 2));
assertEquals(1000000006, modDivide(1000000006, 1));
9. 总结
本文系统实现了六大模运算操作：
- ✅ 模加法
- ✅ 模减法
- ✅ 模乘法
- ✅ 模幂运算
- ✅ 模乘法逆元
- ✅ 模除法
关键结论：
- 模乘法逆元和模除法要求操作数与模数互质
- 所有中间结果通过
minSymmetricMod()优化数值范围- 乘法/幂运算必须使用
long类型防止溢出
完整代码见 GitHub仓库。