算法笔记(1)：疾速幂
疾速幂（Exponentiation by squaring，平方求幂）是一种简略而无效的小算法，它能够以![[公式]](https://www.zhihu.com/equatio…
让咱们先来思考一个问题： 7 的 10 次方，怎么算比拟快？
办法 1：最奢侈的想法，77=49，497=343，… 一步一步算，共进行了 9 次 乘法。
这样算无疑太慢了，尤其对计算机的 CPU 而言，每次运算只乘上一个个位数，无疑太屈才了。这时咱们想到，兴许能够拆分问题。
办法 2：先算 7 的 5 次方，即 7 7777，再算它的平方，共进行了 5 次 乘法。
但这并不是最优解，因为对于“7 的 5 次方”，咱们依然能够拆分问题。
办法 3：先算 7 7 得 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 1000000007
typedef 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 1000000007
typedef 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;
}