快速幂
原理
复杂度：
只要把指数位拆分，就可以实现复杂度的骤减。
实现思路
- 拆分二进制，取出每一位上的值。（移位）
- 如果值为 1 ，则乘。
实现代码
int fast_pow(int a, int b) {
int ans = 1, base = a;
while (b > 0) {
if (b & 1) ans *= base;
base *= base;
b >>= 1;
}
return ans;
}
大数取模
原理
实现思路
-
大数幂取模：乘数取模后相乘再取模。
-
大数取模：累加时取模。
代码
int fast_pow_mod(int a, int b, int p) {
int a1 = a, t = 1;
while (b > 0) {
if (b & 1)
t = (t % p) * (a1 % p) % p;
a1 = (a1 % p) * (a1 % p) % p;
b>>=1;
}
return t % p;
}
int fast_mod(string s, int m) {
int sum = 0;
for (auto c:s) {
sum = (sum * 10 + c - '0') % m;
}
return sum;
}
