快速幂和取余运算
2018-8-28 更新
听说有这么一种算法能够
让计算机很快地求出a^b
暴力相乘的话,电脑要计算
原理 I
(1)如果将
(2)
(3)将
比如
为什么要这样表示?因为在快速幂的过程中,我们会把
过程会是这样:
(好长,可以不看,如果要阅读下面的模拟过程的话,要慢慢地看噢)
·假设我们拿到了
·以电脑视角稍稍观察一下
·制作一个
·制作一个
while(b > 0)
{
·循环一。看,
if(b & 1)
ans *= base;
/*关于 b & 1:
“&”美名曰“按位与”。
x & y 是二进制 x 和 y 的每一位分别进行“与运算”的结果。
与运算,即两者都为 1 时才会返回 1,否则返回 0。
那么 b & 1
二进制
b = 1011
1 = 0001
b&1 = 0001
因为 1(二进制)的前面几位全部都是 0,
所以只有 b 二进制最后一位是 1 时,b & 1 才会返回 1。
挺巧妙的,并且很快。)*/
·然后
base *= base;
同时
b >>= 1;
它把(二进制的)自己每一位都往右移动了。原来的最后第二位,变成了最后第一位!
}
·循环二,再看看
·
·循环三,可是
·循环四,
总的来说,如果
实现
int quickPower(int a, int b)//是求a的b次方
{
int ans = 1, base = a;//ans为答案,base为a^(2^n)
while(b > 0)//b是一个变化的二进制数,如果还没有用完
{
if(b & 1)//&是位运算,b&1表示b在二进制下最后一位是不是1,如果是:
ans *= base;//把ans乘上对应的a^(2^n)
base *= base;//base自乘,由a^(2^n)变成a^(2^(n+1))
b >>= 1;//位运算,b右移一位,如101变成10(把最右边的1移掉了),10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
}
return ans;
}
原理 II
没错快速幂有很多种理解方式。
这是2017年NOIP普及组的完善程序第1题,这里提示的思路和上面不一样。
从头开始。若当前
若当前
也是稍稍模拟一下比较好理解。
·假设我们拿到了
·第一层循环。
·第二层循环几乎独立于第一层存在。
·第三层循环,
·第四层循环,
代码和上面一样。因为
取余运算
快速幂经常要结合取余运算。这里也讲一点。
取余运算有一些好用的性质,包括:
证明都很简单,如果要说服自己的话拿起笔试试吧。可设
于是快速幂过程中可以
while(b > 0)
{
if(b & 1)
{
ans *= base;
ans %= m;
}
base *= base;
base %= m;
b >>= 1;
}
能保证这样下来最后的结果与“先乘到最后,再取余”的结果一样。