加减乘除的取模运算
某些题目，由于要计算的答案非常大（超出64位整数的范围），会要求把答案对 109 + 7取模。如果在计算中途没有处理得当的话，会出现WA（错误）或则TLE（超时）。
例如计算多项乘积时，如果没有中途及时取模，乘法结果会溢出（例如C/C++），从而得到非预期的答案 。对于 Python 来说，虽然没有溢出，但是大整数（big integer）之间的运算不是 O(1)，可能会导致LTE。
加法和乘法的取模
一般涉及到取模（$\bmod$）的题目，会用到如下两个恒等式 $$ \begin{align} (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 \\ \end{align} $$
证明：根据带余除法，∀a ∈ 𝕫，都可以表示为a = qm + r (m ≠ 0)，其中整数q为a除以m的商（quotient），整数r为a除以m的余数（remainder），即r = a mod m。
设a = q1m + r1，b = q2m + r2。 第一个恒等式： $$ \begin{align} (a+b) \bmod m &= (q_1 m + r_1 +q_2 m + r_2) \bmod m \\ &=((q_1 + q_2)m + r_1 + r_2) \bmod m \\ &=(r_1 + r_2) \bmod m \end{align} $$ 又因为r1 = a mod m，r2 = b mod m有： (a + b) mod m = ((a mod m) + (b mod m)) mod m
第二个恒等式： $$ \begin{align} (a\cdot b) \bmod m &= ((q_1 m + r_1)(q_2 m + r_2)) \bmod m \\ &= (q_1 q_2 m^2 + (q_1 r_2 + q_2 r_1)m + r_1 r_2) \bmod m \\ &=(r_1 r_2) \bmod m \end{align} $$
同样有： (a ⋅ b) mod m = ((a mod m) ⋅ (a mod m)) mod m
根据这两个恒等式，我们可以在计算过程中（例如循环中），对加法和乘法的结果取模，而不是在计算最终结果后再取模。
注意：如果涉及到幂运算，不能随意取模。如果指数为整数，可以用快速幂。
如果计算过程中有减法，可能会产生负数，处理不当也会导致 WA。如何正确处理这种情况呢？
同余
首先引入同余（congruence modulo） 的概念。 两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作： a ≡ b (mod m)
例如42 ≡ 12 (mod 10)，因为42和12都可以被10整除，余数都是2。
负数的取模
对于负数，我们可以将其转化为对应的非负数再取模。例如，−17 mod 10可以转化为((−17 mod 10) + 10) mod 10 = (−7 + 10) mod 10，结果是3。 也就是说，如果我们发现 (x mod m) < 0，可以加上一个m，得到非负数。
为避免判断x mod m < 0，可以写成 (x mod m + m) mod m
这样无论x是否为负数，运算结果都会落在区间[0, m − 1]中。
除法的取模
如果要计算$\frac{24}{8} \bmod 5$，如果像加法或乘法处理，写成$\frac{24 \bmod 5}{8 \bmod 5} \bmod 5 = \frac{4}{3}$，明显不是正确答案3。先有结论：
如果p是一个质数，a是b的倍数且b和p互质，那么有 $$ \frac{a}{b} \bmod p = (a \cdot b^{p-2}) \bmod p $$
如果实际题目中推导出了包含除法的求余式，可以用上式转换成乘法，并用快速幂计算bp − 2 mod p。
证明：
- 引理1： 当p是质数且1 ≤ i ≤ p − 1时，有 Cpi ≡ 0 (mod p)
其中 $$ \mathrm{C}_p^i = \frac{p!}{i!(p-i)!} $$ 证明：当p是质数且1 ≤ i ≤ p − 1时，$\frac{p!}{i!(p-i)!}$分母一定不含p，由于分子中包含p且Cpi为整数，所以Cpi一定能被p整除，即Cpi ≡ 0 (mod p)。
- 引理2： 根据二项式定理，有 $$ (x+y)^p = \sum_{k=0}^{p}{\mathrm{C}_p^k x^{p-k} y^k} = \sum_{k=0}^{p}{\mathrm{C}_p^k x^k y^{p-k}} $$
当p为质数，且x, y ∈ 𝕫时，除去k = 0和k = p两项，根据引理1，其余项与0关于p同余。即 $$ \sum_{k=1}^{p-1}{\mathrm{C}_p^k x^{p-k} y^k} \equiv 0 \pmod p $$ 拆分 $$ \begin{align} (x+y)^p &= \mathrm{C}_p^0 x^p y^0 + \sum_{k=1}^{p-1}{\mathrm{C}_p^k x^{n-k} y^k} + \mathrm{C}_p^p x^0 y^p \\ &=x^p + y^p + \sum_{k=1}^{p-1}{\mathrm{C}_p^k x^{n-k} y^k} \end{align} $$
于是当p为质数，且x, y ∈ 𝕫时，有： (x + y)p ≡ xp + yp (mod p)
根据费马小定律，对任意整数a和任意质数p，有： ap ≡ a (mod p) 证明：当a = 0时，0p ≡ 0 (mod p)成立； 已知引理2，通过归纳法，我们可以得到： (x1 + ... + xn)p ≡ x1p + ... + xnp (mod p)
如果将a展开为a个1相加，a = 1 + ... + 1,代入上式有： ap ≡ (1 + ... + 1)p ≡ 1p + ... + 1p ≡ a (mod p)
根据数学归纳法，原命题对于 a ≥ 0 成立。对于a < 0的情况同理，证明完毕。
如果a不是p的倍数，费马小定理也可以写成更加常用的一种形式： ap − 1 ≡ 1 (mod p) 如果a是p的倍数，显然有：ap − 1 ≡ 0 (mod p)。
在a不是p的倍数的前提下，两边同时乘以$\frac{b}{a}$，有 $$ b \cdot a^{p-2} \equiv \frac{b}{a} \pmod p $$
即 $$ \frac{b}{a} \bmod p = (b \cdot a^{p-2}) \bmod p $$
总结
1 | // 如果取模到 [0, MOD-1] 中，无论正负 |