大数求余问题: 在仅使用 int32 类型存储的前提下, 计算 \(x^a\ \text{mod}\ p\) (即 \(x^a\ \%\ p\)).
基本的运算规则: \((xy)\ \%\ p = [(x \ \% \ p)(y \ \% \ p)] \ \% \ p\)
循环求余
当 \(x < p\) 时,
\[x^a \ \% \ p = [(x^{a-1} \ \% \ p)(x \ \% \ p)] \ \% \ p = [(x^{a-1} \ \% \ p)x]\ \% \ p
\]
利用此公式, 可以通过循环操作依次求 \(x^1, x^2,\cdots, x^{a-1}, x^a\) 对 \(p\) 的余数
# 求 (x^a) % p -- 循环求余法
def remainder(x, a, p):rem = 1for _ in range(a):rem = (rem * x) % preturn rem
时间复杂度为 \(O(a)\)
快速幂
\[x^a \ \% \ p = (x^2)^{a/2} \ \% \ p = (x^2 \ \% \ p)^{a/2} \ \% \ p
\]
具体要看 \(a\) 的奇偶性:
\[x^a \ \% \ p =
\left\{\begin{matrix}
(x^2 \ \% \ p)^{a//2} \ \% \ p & , a 为偶数 \\
[x(x^2\ \%\ p)^{a//2}] \ \% \ p &, a 为奇数
\end{matrix}\right.
\]
时间复杂度为 \(\log a\) .
十进制正整数 \(a\) 的二进制形式为 \(b_m\cdots b_2b_1b_0\) , 则 \(x^a = x^{2^{m}b_m} \times \cdots \times x^{2^1 b_1}\times x^{2^{0}b_0}\). 计算 \(x^1, x^2, x^4, \cdots , x^{2^m}\) 的值:
# 求 (x^a) % p -- 快速幂求余
def remainder(x, a, p):rem = 1while a > 0:if a & 1: rem = (rem * x) % px = (x * x) % pa >>= 1return rem