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

首先解释一下为什么喜欢用这个数字。

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

同余定理

快速幂取模

假设我们面对的题目是,其中三个数字的范围是。把 b 表示成二进制。

那么就可以表示为:

如果等于 0 的话,那么就等于 1,可以去掉了;否则就是变成,设,递推关系就变成

实现

用 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. 快速幂取模算法↩︎