例题
https://ac.nowcoder.com/acm/contest/392/B?&headNav=acm
这题快速幂和快速乘都包括了
快速幂
应用
- 相对于正常的O(n)复杂度的求a的n次幂，要快一些，复杂度为O(logn)。
- 快速幂可以算
pow(a, n) % mod;
原理
知道原理的基础上代码好记一些
比如我们要求a ^ b，那么b是可以用二进制表示的，比如a = 2, b = 11，
b的二进制为1011，即b = 2 ^ 0 + 2 ^ 1 + 2 ^ 3
所以a ^ b = a ^ (2 ^ 0 + 2 ^ 1 + 2 ^ 3) = a ^ (2 ^ 0) * a ^ (2 ^ 1) * a ^ (2 ^ 3)
也就是a ^ b = a ^ 1 * a ^ 2 * a ^ 8
即：如果b的二进制形式的第i位为1，结果就乘以a * (2 ^ i)
补充：记得当等于0时，快速幂的返回结果应该返回1！
代码
long long Mode(long long a, long long b, long long mode)
{
if (b == 0){
return 1l % p;
}
long long sum = 1; // 表示结果
a = a % mode; // 为了保险先取个模
while (b) { // 等价于b != 0
if (b & 1) // b的最低位如果为1的话就乘
sum = (sum * a) % mode;
b >>= 1; // 右移，继续判断下一位
a = (a * a) % mode;
// a是拿来记录2的多少次幂的，根据循环次数依次取值为1, 2 , 4, 8, 16
}
return sum;
}
快速乘
跟快速幂的原理类似
IMG_0176.PNG
通过二进制的竖式乘法可以看见，当b的第i位是1的时候，最后的结果就会加上 a * (2 ^ i) (a左移相当于a * 2)
代码
long long multiply(long long a, long long b, long long mode){
long long ans = 0;
while (b){
if (b & 1){
ans = (ans + a) % mode;
}
a = (a + a) % mode;
b >>= 1;
}
return ans;
}
