0%

快速幂取模算法

刷题的过程中,有时候的输出结果需要对1×e9+71 \times e^9 + 7 取余数。这其实是 N 是一个很大的数字,已经设置超过了 long long 能够表示的范围内了。这里需要引入快速幂取模算法[1]

首先解释一下为什么喜欢用1×e9+71 \times e^9 + 7 这个数字。

  1. 10 位数字中的最小质数
  2. 该数相加不超过 int,相乘不超过 long long

同余定理

(a×b)modc=(amodc)×(bmodc)modc\left(a \times b\right) \mod c = \left(a \mod c\right) \times \left(b \mod c\right) \mod c

快速幂取模

假设我们面对的题目是abmodca^b \mod c,其中三个数字的范围是a1a\leq1be5b\geq e^5c=e9+7c= e^9 +7。把 b 表示成二进制。

b=b0×20+b1×21+b2×22++bn×2nb = b_0 \times 2^0 + b_1 \times 2^1 + b_2 \times 2^2 + \dots + b_n \times 2^n

那么aba^b 就可以表示为:

ab=ab0×20×ab1×21×ab2×22××abn×2na^b = a^{b_0 \times 2^0} \times a^{b_1 \times 2^1} \times a^{b_2 \times 2^2} \times \dots \times a^{b_n \times 2^n}

如果bib_i 等于 0 的话,那么abi×2ia^{b_i \times 2^i} 就等于 1,可以去掉了;否则就是变成a2ia^{ 2^i},设A(n)=a2iA(n)=a^{ 2^i},递推关系就变成A(n)=A(n1)2A(n) = A(n-1)^2

实现

用 C++ 语言实现一次快速幂取模算法。

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;

ll mod_pow(ll a, ll b, ll c) {
ll res = 1;
a %= c;
while (b > 0) {
if (b & 1) res = res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}

  1. 快速幂取模算法 ↩︎