快速幂和取余运算
学委
2018-07-02 13:02:22
*2018-8-28 更新*
听说有这么一种算法能够
## 让计算机很快地求出$a^b$
暴力相乘的话,电脑要计算 $b$ 次。用快速幂,计算次数在 $log_2(b)$ 级别,很实用。
## 原理 I
(1)如果将 $a$ 自乘一次,就会变成 $a^2$ 。再把 $a^2$ 自乘一次就会变成 $a^4$ 。然后是 $a^8$…… 自乘 $n$ 次的结果是 $a^{2^{n}}$ 。对吧……
(2)$a^xa^y = a^{x+y}$,这个容易。
(3)将 $b$ 转化为二进制观看一下:
比如 $b = (11)_{10}$ 就是 $(1011)_{2}$ 。从左到右,这些 $1$ 分别代表十进制的 $8,2,1$。可以说 $a^{11} = a^8 × a^2 × a^1$。
为什么要这样表示?因为在快速幂的过程中,我们会把 $a$ 自乘为 $a^2$,然后 $a^2$ 自乘为 $a^4$……像上面第一条说的。
___
___
**过程会是这样:**
(好长,可以不看,如果要阅读下面的模拟过程的话,要慢慢地看噢)
·假设我们拿到了 $a$,并且 $b = 11$。想求 $a^{11}$,但是又不想乘11次,有点慢。
·以电脑视角稍稍观察一下 $b = 11$,二进制下是 $b = 1011$。
·制作一个 $base$。现在 $base = a$,表示的是,$a^1 = a$。待会 $base$ 会变的。
·制作一个 $ans$,初值 $1$,准备用来做答案。
___
```cpp
while(b > 0)
{
```
·循环一。看,$b$(二进制)的最后一位是 $1$ 吗?
是的。这代表 $a^{11} = a^8 × a^2 × a^1$ 中的“ $× a^1$ ”存在。所以 $ ans *= base $。
```cpp
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$ 努力上升,他通过自乘一次,使自己变成 $a^2$。
```cpp
base *= base;
```
同时
```cpp
b >>= 1;
```
它把(二进制的)自己每一位都往右移动了。原来的最后第二位,变成了最后第一位!$b = (101)_2$。
```cpp
}
```
___
·循环二,再看看 $b$,最后一位还是 $1$。这说明有“ $× a^2$ ”,$ans *= base$。
·$base$ 继续努力,通过 $base *= base$ 让自己变成了 $a^4$。然后 $b$ 也右移
一位。$b = 10$。
___
·循环三,可是 $b$ 的最后一位不再是 $1$ 了,说明不存在“ $× a^4$ ”。$base$ 自我升华,达到了 $a^8$。且 $b >>= 1$。这一步中,答案没有增加,可是毕竟 $b > 0$,还有希望。
___
·循环四,$b$ 的最后一位是 $1$,这说明“ $×a^8$ ”的存在。$ ans *= base $。由于 $b$ 再右移一位就是 $0$ 了,循环结束。
___
___
总的来说,如果 $b$ 在二进制上的某一位是 $1$,我们就把答案乘上对应的 $a^{2^{n}}$。不懂的话,请结合代码理解~
## 实现
```cpp
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题,这里提示的思路和上面不一样。
![](https://cdn.luogu.com.cn/upload/pic/30947.png)
从头开始。若当前 $p$ 为偶数,咱们不着急,只需把 $x$ 自乘,然后 $ p /= 2$ (即考虑下一层,下几层会帮我们乘上 $(x^2)^{p/2}$的)。
若当前 $p$ 为奇数,说明 $x^p = x*(x^2)^{(p-1)/2}$ 中前面那个 $x$ 的存在,$ans *= x$。然后继续考虑下一层(下几层会帮我们乘上 $(x^2)^{(p-1)/2}$的)。注意,这里的 $x$ 不是指题目开始给出的 $x$,而是当前层的 $x$ 应有的值,这跟上面的 $base$ 是一样的。
___
____
**也是稍稍模拟一下比较好理解。**
·假设我们拿到了 $x = 3$,并且 $p = 11$。想求 $3^{11}$。
·第一层循环。$b = 11$,一个奇数。将 $3^{11}$ 分解为 $3^1 * (3^2)^5$ 来看。本层只需把 $ans *= 3^1$。那后面的呢?我们到下一层再搞定。下几层的总目标是让 $ans *= (3^2)^5$,也就是让 $ans *= 9^5$。**来到下一层的方法是 $x = 3*3 = 9$ 且 $b = 11 / 2 = 5$。**
·第二层循环几乎独立于第一层存在。$b = 5$,一个奇数。将 $9^{5}$ 分解为 $9^1 * (9^2)^2$ 来看。本层只需把 $ans *= 9^1$。那后面的呢?我们到下一层再搞定。下几层的总目标是让 $ans *= (9^2)^2$,也就是让 $ans *= 81^2$。于是 $x = 9*9 = 81$ 且 $b = 5 / 2 = 2$。
·第三层循环,$b = 2$,不是奇数,不着急,只把 $81^2$ 当作 $(81^2)^1$。下几层的总目标是让 $ans *= (81^2)^1$。于是 $x = 81 * 81 = 6561$,$b = 2 / 2 = 1$。
·第四层循环,$b = 1$,是奇数。这时候已经不用看成什么分解了,$ans *= 6561$ 就可完成总目标。$b / 2$ 为 $0$。结束循环。
___
___
代码和上面一样。因为 $b \& 1$ 与 $b \mod 2 == 1$ 等效。$b /= 2$ 与 $b >>= 1$ 等效。
![](https://cdn.luogu.com.cn/upload/pic/30953.png)
## 取余运算
快速幂经常要结合取余运算。这里也讲一点。
取余运算有一些好用的性质,包括:
$(A+B) \mod b = (A \mod b + B \mod b) \mod b$
$(A×B) \mod b = ((A \mod b) × (B \mod b)) \mod b$
证明都很简单,如果要说服自己的话拿起笔试试吧。可设 $A = k_A × b + R_A$……
于是快速幂过程中可以
```cpp
while(b > 0)
{
if(b & 1)
{
ans *= base;
ans %= m;
}
base *= base;
base %= m;
b >>= 1;
}
```
能保证这样下来最后的结果与“先乘到最后,再取余”的结果一样。