Modular Arithmetic 模运算

简介

在模运算中，我们不是直接处理整数本身，而是处理它们除以 $m$ 后的余数。我们称这个过程为取模 $m$。例如，如果我们取 $m = 23$，那么我们不是处理 $x = 247$，而是使用 $x \bmod 23 = 17$。

通常，$m$ 会是一个大素数，题目中会给出；最常见的两个值是 $10^9 + 7$ 和 $998244353 = 119 \cdot 2^{23} + 1$。

模运算用于避免处理会溢出内置数据类型的数字，因为我们可以根据以下公式取余数：

• $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
• $(a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m$
• $(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$
• $a^b \bmod m = (a \bmod m)^b \bmod m$

---

模幂运算

为什么需要快速幂？

计算 $x^n \bmod m$ 时，如果直接使用循环乘 $n$ 次，时间复杂度是 $O(n)$。但当 $n$ 达到 $10^9$ 甚至更大时，这种方法就太慢了。

二进制幂次方

二进制幂次方（Binary Exponentiation）可以将时间复杂度降到 $O(\log n)$。

核心思想：将指数 $n$ 分解为二进制表示。例如： $$5^{10} = 5^{1010_2} = 5^8 \cdot 5^2$$

如果我们知道 $x^1, x^2, x^4, \dots, x^{2^{\lfloor \log_2 n \rfloor}}$，就可以用 $O(\log n)$ 的时间计算出 $x^n$。

实现

MOD = 10**9 + 7

def pow_mod(a, b, mod):
    """计算 a^b mod mod"""
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

Python 内置的 pow 函数已经实现了快速幂，可以直接使用：

MOD = 10**9 + 7

for _ in range(int(input())):
    first, second = map(int, input().split())
    print(pow(first, second, MOD))

---

模逆元

什么是模逆元？

模逆元相当于实数中的倒数。要将 $a$ 除以 $b$，可以乘以 $b$ 的模逆元。

对于素数模 $p$，$a$ 的模逆元定义为满足以下条件的数 $a^{-1}$： $$a \cdot a^{-1} \equiv 1 \pmod{p}$$

例如，$2$ 模 $p = 10^9 + 7$ 的逆元是 $i = \frac{p+1}{2} = 5 \cdot 10^8 + 4 = 500000004$。

验证： $$2 \times 500000004 \equiv 1000000008 \equiv 1 \pmod{1000000007}$$

费马小定理

费马小定理（不要与费马大定理混淆）指出，所有不被 $p$ 整除的整数 $a$ 都满足： $$a^{p-1} \equiv 1 \pmod{p}$$

因此： $$a^{p-2} \cdot a \equiv 1 \pmod{p}$$

所以 $a^{p-2}$ 就是 $a$ 模 $p$ 的逆元。

实现

MOD = 10**9 + 7

# 方法1：使用费马小定理
x = pow(2, MOD - 2, MOD)
print(x)  # 500000004
assert 2 * x % MOD == 1

扩展欧几里得算法

我们也可以通过扩展欧几里得算法求模逆元：

def modinv(x, mod):
    """扩展欧几里得算法求模逆元"""
    if x <= 1:
        return x
    return mod - mod // x * modinv(mod % x, mod) % mod

预计算逆元

如果需要频繁计算多个数的模逆元，可以利用以下递推公式预计算：

MOD = 10**9 + 7
inv = [0] * MOD
inv[1] = 1
for i in range(2, MOD):
    inv[i] = MOD - MOD // i * inv[MOD % i] % MOD

这样可以在 $O(MOD)$ 时间内预处理所有 $[1, MOD)$ 范围内数的逆元，之后每次查询只需 $O(1)$。

---

注意事项

1. 除零错误：必须确保不尝试除以 0
2. 取模后的零：要注意在应用模运算后，一个非零数可能会变成零，因此在对非常数值进行除法运算时要格外小心
3. 性能：由于计算模逆元需要 $O(\log p)$ 的时间，在循环内部频繁使用除法会显著增加程序的运行时间。如果多次使用同一个数的模逆元，预先计算它是更好的选择