一、快速幂定义：
快速幂就是指：用 O (log n) 的时间算出 a^n，按理来说我们用普通的for循环也能算出结果，但是for循环会浪费很长的时间，这样写绝对会让代码时间超限，所以我们可以采用快速幂这可以极大缩短运行时间以解决比赛中时间超限的问题举个例子：
如果我们要计算10的18，先用for循环尝试一下会发现我们的循环要运行1e18次，这显然不可能实现，但是如果我们该用快速幂就只需要运行60次左右。
二、核心原理
理论：我们知道任何一个指数幂都可以拆成2的幂次相加例：
13的 二进制表示为 1101 即表示为 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
所以13可以由8+4+1组成
代码中的式子表示一般写成：abmodp（p指对p取余）
这就是指数幂最核心的思想，现在我们将去利用这个思想去解决时间超限
我们先说一下
三、实际应用
若想熟练应用快速幂我们首先要搞懂什么是位运算中的&和>>符号
首先是&
使用规则：两个数同是1才得到1，就像这样
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
我们一般也可以用x&1来判断x的奇偶性
接下来是>>
使用规则：无符号的话高位补0，有符号的话高位补符号位，例：
x << n 等价于 x/2^n（不溢出时）
8: 0000 1000
8 >> 1: 0000 0100 (4)
8 >> 2: 0000 0010 (2)
总的来说右移多少位就是除以2的几次方、
这两个序号了解后我们来看一下快速幂最基本的核心代码
// 快速幂函数
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
a %= mod;
while(b)
{
if(b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
我们来总结一下主要步骤：
1.让a对mod取模
2.判断b的二进制是否有1
3.若有1更新res的值为res*a%mod;
4.若没有1则不用对res进行更新
5.先将a的值变为a*a%mod
6.最后将b除以2得到一个新的b值
注意：第三步和第五步一定要记得取模否则数据可能会因为过大而溢出。
现在我们给出一些实际的例题
求 abmodm，数据范围：1≤a,b≤1018
#include <iostream>
using namespace std;
typedef long long ll;
// 快速幂：a^b % mod
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
a %= mod; // 先取模防止溢出
while(b > 0)
{
if(b & 1) // 指数二进制末位为1，乘到答案里
res = res * a % mod;
a = a * a % mod; // 底数平方
b >>= 1; // 指数右移1位 = 除以2
}
return res;
}
int main()
{
// 求 2^10 % 1000
cout << qpow(2, 10, 1000) << endl;
return 0;
}
