快速幂讲解（很重要的算法）

2021/11/7 17:14:04

编程Tag： 算法 return 快速讲解复杂度 MUL ll ans

本文主要是介绍快速幂讲解（很重要的算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

什么是快速幂

快速幂是对于求 ${a}^{b}%{m}$ 的一种快速的算法。 ${a}^{b}%{m}$ 的解法有很多种，我们从暴力法讲起：

一、暴力算法

众所周知， ${a}^{b}$ 的定义为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)

优点与缺点

优点是写法简洁，缺点是速度太慢，在 $1\leqslant {b}\leqslant {10}^{18}$ 的数据范围下根本撑不住。

二、二分幂

二分幂的想法如下：

如b为奇数， ${a}^{b} = {a}^{b \div 2} * {a}^{b \div 2} * {a}$

如b为偶数， ${a}^{b} = {a}^{b \div 2}*{a}^{b \div 2}$

因此可以写出递归代码：

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拆成二进制 ${b}={a}_{n} \times {2}^{n} + {a}_{n-1} \times {2}^{n-1} + ... + {a}_{0} \times {2}^{0}$

再对每一位进行分解：

如果为1，就算，

否则，就不算。

举个例子：由于 $11 = \left ( 1011 \right )_2$ ，所以 ${a}^{11} = {a}^{8} + {a}^{2} + {a}^{1}$

而我们直接用一个循环统计 ${a}^{1}, {a}^{2}, {a}^{4}...$ 就行了。

不多说，直接上代码：

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呢？（啊？）

这篇关于快速幂讲解（很重要的算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！