如果我问在座的各位，快速幂是什么，恐怕没几个人能答上来……

但是，快速幂这么重要的知识，怎么能不学呢？

什么是快速幂

快速幂是对于求的一种快速的算法。的解法有很多种，我们从暴力法讲起：

一、暴力算法

众所周知，的定义为b个a相乘，因此只需要用一个循环就能搞定了：

#define LL long long
LL PowerMod(LL a, LL b, LL m) {
    int ans = 1;
    for (int i = 0; i < b; i++) { // 关键！
        ans = (ans * a) % m;
    }
    return ans;
}

评估

时间复杂度：O(b)

空间复杂度：O(1)

优点与缺点

优点是写法简洁，缺点是速度太慢，在的数据范围下根本撑不住。

二、二分幂

二分幂的想法如下：

如b为奇数，

如b为偶数，

因此可以写出递归代码：

LL PowerMod2(LL a, LL b, LL m) {
    if (b == 0) { // 递归边界
        return 1;
    }
    LL mul = PowerMod2(a, b / 2, m); // 求a^(b/2)
    if (b & 1) { // 用位运算代替奇偶性判断
        return mul * mul * a;
    }
    return mul * mul;
}

评估

时间复杂度：O(log2(b)) （当然了递归比较慢）

空间复杂度：O(log2(b)) （递归需占用内存）

优点和缺点

优点是速度变快，缺点是需要占用空间，不过一般O(log2(b))的空间复杂度足够了。

三、快速幂：

终于到正题了！快速幂的想法如下：

先把b拆成二进制

再对每一位进行分解：

如果为1，就算，

否则，就不算。

举个例子：由于 ，所以

而我们直接用一个循环统计就行了。

不多说，直接上代码：

LL PowerMod3(LL a, LL b, LL m) {
	LL ans = 1;
	a %= m; // 预处理
	for (; b > 0; b /= 2) { // 获得每一位
		if (b & 1) { // 如果这一位是一
			ans = ans * a % m;
		}
		a = a * a % m; // 注：a * a不是原来的a * a了！想想是什么？
	}
	return ans;
}

题外话

1、这边的都是模板……（废话）

3、你们知道只算幂怎么办了吧？（废话）

4、那你们有没有看到没有2呢？（啊？）