C++基础算法【倍增思想-快速幂】流食般投喂

本编要求带着理解记住快速幂的模板，对倍增思想-快速幂有底层理解。

倍增思想-快速幂：

🧀这个算法是 不超时、不超类型存储数据范围 快速求解一个幂。

倍增思想的体现：

📌不断通过自己和自己相乘，达到倍增效果。

📌此时，这个只能用于快速求解 "a^特定偶数次方" 的数。

借助 "二进制"解决超时问题：

🧀借助 "二进制" 是做到不超时。

🍞借助 "二进制" 可以在结合上文所体现的倍增思想，做到快速求解 "a^任意次方" 的数。

📌二进制用于幂的指数部分。

• 例如 "2^11" 这个数，借助二进制拆解他的指数部分：

2^3 2^2 2^1 2^0
| | | |
8 4 2 1
| | | |
1 0 1 1
即 11 = (1011)二进制 = 1*8 + 0*4 + 1*2 + 1*1
2^11 = 2^(1011)二进制 = 2^(8 + 0 + 2 + 1) = 2^8 * 2^0 * 2^2 * 2^1
= 2^8 * 1 * 2^2 * 2^1
🧀指数由十进制->二进制->十进制，
目的是：把一个指数很大的幂，通过其性质，拆解成多个指数小的幂相乘，
而这些多个指数小的幂，可以在自己和自己相乘的倍增中找到。
📌指数拆解成二进制数后，二进制时，二进制位为 1 的，要找，就在 ret 乘上对应权值，
为 0，不要找，就在统计结果的 ret 上乘 1。

取模解决超类型存储范围及其扩展：

算法思想转化乘代码实现：

#include<iostream>

using namespace std;

typedef long long LL;

// a^b % p 的值
LL qpow(LL a, LL b)
{
LL ret = 1;
while(b)
{
if (b & 1) ret = ret * a % p;
a = a * a % p;
b >>= 1;
}
}

int main()
{
//…

return 0;
}