算法笔记(1)：疾速幂
疾速幂（Exponentiation by squaring，平方求幂）是一种简略而无效的小算法，它能够以![[公式]](https://www.zhihu.com/equatio...
让咱们先来思考一个问题：7的10次方，怎么算比拟快？
办法1：最奢侈的想法，77=49，497=343，... 一步一步算，共进行了9次乘法。
这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时咱们想到，兴许能够拆分问题。
办法2：先算7的5次方，即77777，再算它的平方，共进行了5次乘法。
但这并不是最优解，因为对于“7的5次方”，咱们依然能够拆分问题。
办法3：先算77得49，则7的5次方为4949*7，再算它的平方，共进行了4次乘法。
模拟这样的过程，咱们失去一个在 ![[公式]](https://www.zhihu.com/equatio... 工夫内计算出幂的算法，也就是疾速幂。
递归疾速幂
刚刚咱们用到的，无非是一个二分的思路。咱们很天然地能够失去一个递归方程：
![[公式]](https://www.zhihu.com/equatio...
计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，而后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归进口是a的0次方为1。
递归疾速幂的思路十分天然，代码也很简略（间接把递归方程翻译成代码即可）：
//递归疾速幂int qpow(int a, int n){ if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a; else { int temp = qpow(a, n / 2); return temp * temp; }}留神，这个temp变量是必要的，因为如果不把![[公式]](https://www.zhihu.com/equatio... n /2)*qpow(a, n /2)，那会计算两次![[公式]](https://www.zhihu.com/equatio... ![[公式]](https://www.zhihu.com/equatio... 。
在理论问题中，题目经常会要求对一个大素数取模，这是因为计算结果可能会十分微小，然而在这里考查高精度又没有必要。这时咱们的疾速幂也该当进行取模，此时该当留神，准则是步步取模，如果MOD较大，还该当开long long。
//递归疾速幂（对大素数取模）#define MOD 1000000007typedef long long ll;ll qpow(ll a, ll n){ if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a % MOD; else { ll temp = qpow(a, n / 2) % MOD; return temp * temp % MOD; }}大家晓得，递归尽管简洁，但会产生额定的空间开销。咱们能够把递归改写为循环，来防止对栈空间的大量占用，也就是非递归疾速幂。
非递归疾速幂
咱们换一个角度来引入非递归的疾速幂。还是7的10次方，但这次，咱们把10写成二进制的模式，也就是 ![[公式]](https://www.zhihu.com/equatio... 。
当初咱们要计算 ![[公式]](https://www.zhihu.com/equatio... ，能够怎么做？咱们很天然地想到能够把它拆分为 ![[公式]](https://www.zhihu.com/equatio... . 实际上，对于任意的整数，咱们都能够把它拆成若干个 ![[公式]](https://www.zhihu.com/equatio... 的模式相乘。而这些![[公式]](https://www.zhihu.com/equatio... ![[公式]](https://www.zhihu.com/equatio... 、![[公式]](https://www.zhihu.com/equatio...
咱们先看代码，再来认真斟酌这个过程：
//非递归疾速幂int qpow(int a, int n){ int ans = 1; while(n){ if(n&1) //如果n的以后末位为1 ans *= a; //ans乘上以后的a a *= a; //a自乘 n >>= 1; //n往右移一位 } return ans;}最后ans为1，而后咱们一位一位算：
1010的最初一位是0，所以a^1这一位不要。而后1010变为101，a变为a^2。
101的最初一位是1，所以a^2这一位是须要的，乘入ans。101变为10，a再自乘。
10的最初一位是0，跳过，右移，自乘。
而后1的最初一位是1，ans再乘上a^8。循环完结，返回后果。
这里的位运算符，>>是右移，示意把二进制数往右移一位，相当于/2；&是按位与，&1能够了解为取出二进制数的最初一位，相当于%2==1。这么一等价，是不是看出了递归和非递归的疾速幂的关系了？尽管非递归疾速幂因为牵扯到二进制了解起来略微简单一点，但基本思路其实和递归疾速幂没有太大的出入。
疾速幂的拓展
下面所述的都是整数的疾速幂，但其实，在算 ![[公式]](https://www.zhihu.com/equatio... 时，只有a的数据类型反对乘法且满足结合律，疾速幂的算法都是无效的。矩阵、高精度整数，都能够照搬这个思路。上面给出一个模板：
//泛型的非递归疾速幂template <typename T>T qpow(T a, ll n){ T ans = 1; // 赋值为乘法单位元，可能要依据构造函数批改 while (n) { if (n & 1) ans = ans * a; // 这里就最好别用自乘了，不然重载完*还要重载*=，有点麻烦。 n >>= 1; a = a * a; } return ans;}留神，较简单类型的疾速幂的工夫复杂度不再是简略的 ![[公式]](https://www.zhihu.com/equatio... ，它与底数的乘法的工夫复杂度无关。
例如，矩阵疾速幂的一个经典利用是求斐波那契数列：
（洛谷P1962） 斐波那契数列
题目背景
大家都晓得，斐波那契数列是满足如下性质的一个数列：
![[公式]](https://www.zhihu.com/equatio...
题目形容
请你求出 ![[公式]](https://www.zhihu.com/equatio... 的值。
（以下内容波及到根本的线性代数常识）
设矩阵 ![[公式]](https://www.zhihu.com/equatio... ，咱们有![[公式]](https://www.zhihu.com/equatio...
于是 :
![[公式]](https://www.zhihu.com/equatio...
这样，咱们把原来较为简单的问题转化成了求某个矩阵的幂的问题，这就能够利用疾速幂求解了。
#include <cstdio>#define MOD 1000000007typedef long long ll;struct matrix{ ll a1, a2, b1, b2; matrix(ll a1, ll a2, ll b1, ll b2) : a1(a1), a2(a2), b1(b1), b2(b2) {} matrix operator*(const matrix &y) { matrix ans((a1 * y.a1 + a2 * y.b1) % MOD, (a1 * y.a2 + a2 * y.b2) % MOD, (b1 * y.a1 + b2 * y.b1) % MOD, (b1 * y.a2 + b2 * y.b2) % MOD); return ans; }};matrix qpow(matrix a, ll n){ matrix ans(1, 0, 0, 1); //单位矩阵 while (n) { if (n & 1) ans = ans * a; a = a * a; n >>= 1; } return ans;}int main(){ ll x; matrix M(0, 1, 1, 1); scanf("%lld", &x); matrix ans = qpow(M, x - 1); printf("%lld\n", (ans.a1 + ans.a2) % MOD); return 0;}