关于余数的定理
在数论中，余数（模运算）相关的定理是解决许多算法问题的基础。以下是几个核心定理及其在算法中的应用场景：
1. 同余定理（Congruence Theorem）
定义：若两个整数 (a) 和 (b) 满足 (a \equiv b \pmod{m})，则 (m) 整除 (a-b)，即存在整数 (k) 使得 (a = b + km)。
应用：
- 判断子数组和是否为k的倍数：
若前缀和 (S_i \equiv S_j \pmod{k})，则子数组 (nums[j+1…i]) 的和为 (S_i - S_j = km)（即k的倍数）。
例如：LeetCode 523、974题。
2. 模运算的基本性质
对于任意整数 (a, b, c) 和正整数 (m)：
- 加法：((a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m)
- 减法：((a - b) \mod m = [(a \mod m) - (b \mod m)] \mod m)
- 乘法：((a \times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m)
应用：
- 大数取模优化：避免中间结果溢出，例如计算斐波那契数列模 (10^9+7)。
3. 费马小定理（Fermat’s Little Theorem）
内容：若 (p) 是质数，且整数 (a) 不是 (p) 的倍数，则：
[
a^{p-1} \equiv 1 \pmod{p}
]
推论：(a) 的逆元为 (a^{p-2} \mod p)，常用于模运算下的除法。
应用：
- 快速幂求逆元：计算 (\frac{b}{a} \mod p) 等价于 (b \times a^{p-2} \mod p)（LeetCode 1512题）。
4. 中国剩余定理（Chinese Remainder Theorem, CRT）
内容：对于互质的模数 (m_1, m_2, …, m_n)，方程组：
[
\begin{cases}
x \equiv a_1 \pmod{m_1} \
x \equiv a_2 \pmod{m_2} \
\vdots \
x \equiv a_n \pmod{m_n}
\end{cases}
]
在 (M = m_1 \times m_2 \times … \times m_n) 下有唯一解：
[
x = \sum_{i=1}^n a_i \cdot M_i \cdot y_i \mod M
]
其中 (M_i = \frac{M}{m_i})，(y_i) 是 (M_i) 在模 (m_i) 下的逆元。
应用：
- 分解模数：将大模数分解为多个小质数的乘积，分别处理后合并结果（如RSA加密）。
5. 欧拉定理（Euler’s Theorem）
内容：若 (a) 与 (n) 互质，则：
[
a^{\phi(n)} \equiv 1 \pmod{n}
]
其中 (\phi(n)) 是欧拉函数，表示小于等于 (n) 且与 (n) 互质的数的个数。
特例：当 (n) 为质数时，(\phi(n) = n-1)，退化为费马小定理。
应用：
- 模幂运算优化：计算 (a^b \mod n) 时，若 (a) 与 (n) 互质，则 (a^b \equiv a^{b \mod \phi(n)} \mod n)。
6. 威尔逊定理（Wilson’s Theorem）
内容：若 (p) 是质数，则：
[
(p-1)! \equiv -1 \pmod{p}
]
应用：
- 质数判定：逆定理可用于判断 (p) 是否为质数（但效率低，仅作理论工具）。
在算法题中的高频应用
-
前缀和 + 哈希表：
通过记录余数的首次出现位置，快速判断子数组和是否为k的倍数（如LeetCode 523、974）。 -
大数取模：
处理大数运算时，利用模运算性质避免溢出（如斐波那契数列模 (10^9+7)）。 -
逆元计算：
在模运算下进行除法（如组合数 (C(n, k) \mod p)）。 -
周期性问题：
利用余数判断循环节（如约瑟夫环问题）。
总结
余数定理是连接数学与算法的桥梁，特别是在处理子数组和、大数运算、周期性问题时尤为重要。理解这些定理的核心思想，并熟练运用哈希表等数据结构记录余数状态，是解决相关问题的关键。