快速幂&取模 | Wuhaoda's Blog

快速幂&取模

原理

并没有想象中的这么高大上
只是采用分治的思想
比如:
a^11 = a^8 a^2 a^1
二进制拆分一下, 把11拆成8 2 1

用base一点一点累加a^i 即可
如果题目要求取模
每一步取个膜即可
复杂度是O(log n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
inline long long quickPower(int a, int b) {
int base = a, mo = 1;
while(b > 0) {
if(b & 1) {
mo *= base;
// mo %= n;
}
base *= base;
// base %= n;
b >>= 1;
}
return mo;
}

其中 求的是 a^b
注释掉的是 求 a^b % n