【基础 II】快速幂和取余运算

长沙7喜 2018-10-06

展开全文

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$ ，准备用来做答案。

while(b > 0)
{

·循环一。看， $b$ （二进制）的最后一位是 $1$ 吗？是的。这代表 $a^{11} = a^8 × a^2 × a^1$ 中的“ $× a^1$ ”存在。所以 $ans *= base$ 。

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$ 。

base *= base;

同时

b >>= 1;

它把（二进制的）自己每一位都往右移动了。原来的最后第二位，变成了最后第一位！ $b = (101)_2$ 。

·循环二，再看看 $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}}$ 。不懂的话，请结合代码理解~

实现

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题，这里提示的思路和上面不一样。

从头开始。若当前 $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$ 等效。

取余运算

快速幂经常要结合取余运算。这里也讲一点。

取余运算有一些好用的性质，包括：

$(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$ ……

于是快速幂过程中可以


    while(b > 0)
    {
        if(b & 1)
        {
            ans *= base;
            ans %= m;
        }

        base *= base;
        base %= m;
        b >>= 1;
    }

能保证这样下来最后的结果与“先乘到最后，再取余”的结果一样。

最后推荐一下自己的博客