必知必会数学技巧

模运算技巧

模运算技巧是必须掌握的，主要是几个运算律：

• 加法：(a + b) % k = (a % k + b % k) % k
• 乘法：(a * b) % k = (a % k) * (b % k) % k
• 减法：(a - b) % k = (a % k - b % k + k) % k

减法公式中 + k 的目的是防止结果为负数。例如 (1 - 3) % 5，在有的编程语言中结果可能是 -2，但数学上的模运算结果应该为正，即 (-2 + 5) % 5 = 3。

对于乘法运算律可能有点不容易看出来，下面简单证明一下。假设：

a = Ak + B；b = Ck + D

其中 A,B,C,D 是任意常数，那么：

ab = ACk^2 + ADk + BCk +BD
ab % k = BD % k

又因为：

a % k = B；b % k = D

所以：

(a % k)(b % k) % k = BD % k = ab % k

综上，就可以得到我们化简求模的等式了。

换句话说，对乘法的结果求模，等价于先对每个因子都求模，然后对因子相乘的结果再求模。

乘法运算律是最常用的，因为当 a, b 较大时，可以避免直接计算 (a * b) 的结果溢出。下面的快速幂算法就利用了这个技巧。

快速幂

如何计算 $a^b \pmod k$？如果直接循环 b 次进行乘法，时间复杂度是 $O(b)$。当 b 很大时（例如 $10^9$），这个做法效率太低。

快速幂算法利用了幂运算的性质，按照指数的奇偶性进行递归计算：

$$a^b = \begin{cases} (a^{b/2})^2, & \text{当 b 为偶数} \\ a \cdot a^{b-1}, & \text{当 b 为奇数} \end{cases}$$

每次可以将规模减半，因此时间复杂度为 $O(\log b)$。

参考代码：

// 计算 (a ^ b) % k
long quickPow(long a, long b, long k) {
    long res = 1;
    // 防止 a 大于 k
    a %= k;
    while (b > 0) {
        // 判断奇数，等价于 b % 2 == 1
        if ((b & 1) == 1) {
            res = (res * a) % k;
        }
        a = (a * a) % k;
        // 右移一位，相当于除以 2
        b >>= 1;
    }
    return res;
}

有些编程语言内置了快速幂算法（如 Python 的 pow 函数），可以直接使用。

最大公约数

求两个数的最大公约数（Greatest Common Divisor，简称 GCD）是常见的数学问题。

最大公约数是指能够同时整除两个或多个整数的最大正整数。换句话说，如果 gcd(a, b) = d，那么：

• a % d == 0 且 b % d == 0（d 能整除 a 和 b）
• 不存在比 d 更大的数满足上述条件

举几个例子：

• gcd(12, 18) = 6

  • 12 的约数有：1, 2, 3, 4, 6, 12
  • 18 的约数有：1, 2, 3, 6, 9, 18
  • 公约数有：1, 2, 3, 6，其中 6 最大

• gcd(17, 19) = 1

  • 17 和 19 都是质数，它们只有公约数 1

• gcd(24, 36) = 12

  • 24 的约数有：1, 2, 3, 4, 6, 8, 12, 24
  • 36 的约数有：1, 2, 3, 4, 6, 9, 12, 18, 36
  • 公约数有：1, 2, 3, 4, 6, 12，其中 12 最大

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

最常用的求 GCD 算法是欧几里得算法，核心思想是：

gcd(a, b) = gcd(b, a % b)，直到 b == 0，此时 a 就是最大公约数。

算法的正确性基于一个数学定理：a 和 b 的公约数，同时也是 b 和 a % b 的公约数。

举个例子，计算 gcd(48, 18)：

gcd(48, 18)
= gcd(18, 48 % 18)
= gcd(18, 12)
= gcd(12, 18 % 12)
= gcd(12, 6)
= gcd(6, 12 % 6)
= gcd(6, 0)
= 6

最小公倍数

求两个数的最小公倍数（Least Common Multiple，简称 LCM）。

最小公倍数是指能够同时被两个或多个整数整除的最小正整数。换句话说，如果 lcm(a, b) = m，那么：

• m % a == 0 且 m % b == 0（m 能整除 a 和 b）
• 不存在比 m 更小的数满足上述条件

举几个例子：

• lcm(4, 6) = 12

  • 4 的倍数有：4, 8, 12, 16, 20, 24...
  • 6 的倍数有：6, 12, 18, 24, 30...
  • 公倍数有：12, 24, 36...，其中 12 最小

• lcm(3, 5) = 15

  • 3 的倍数有：3, 6, 9, 12, 15, 18...
  • 5 的倍数有：5, 10, 15, 20, 25...
  • 公倍数有：15, 30, 45...，其中 15 最小

• lcm(7, 7) = 7

  • 两个相同数的最小公倍数就是它本身

最小公倍数可以通过最大公约数算出，这个关系非常重要：

$$\text{lcm}(a, b) = \frac{|a \cdot b|}{\text{gcd}(a, b)}$$

这个公式背后的数学原理是：两个数的乘积等于它们的最大公约数与最小公倍数的乘积，即 a * b = gcd(a, b) * lcm(a, b)。

简单验证一下：

lcm(4, 6) = (4 * 6) / gcd(4, 6) = 24 / 2 = 12
lcm(12, 18) = (12 * 18) / gcd(12, 18) = 216 / 6 = 36

为了防止 a * b 溢出，通常写成：

$$\text{lcm}(a, b) = (a / \text{gcd}(a, b)) * b$$

代码实现：

int lcm(int a, int b) {
    // 先除后乘，防止溢出
    return (a / gcd(a, b)) * b;
}