什么是快速幂
快速幂算法是用来快速计算指数表达式的值的。以前我们求a^b（a的b次方）的值, 我们可以写一个for循环，乘以b次a，时间复杂度为O(b)。当b比较小的时候还可以运用，但是当b很大，比如b=1000000,此时时间复杂度就很高了，我们需要对其进行优化 ——— 快速幂。
快速幂的前置知识
1、二进制构成数字
众所周知，每个十进制数都可以由唯一的二进制数表示
例如：13的 二进制表示为 1101 即表示为 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
即13可以由8+4+1组成
我们不难发现，每一个十进制数都由其对应的二进制数，那么每一个十进制数都可以有1 2 4 8 32 64 … 等这种二的次方数相加得到，并且每一种数只能取1个或0个
再例如 9，其二进制为1001 ， 8+1=9 ，即由1个8和1个1相加得到9
2、位运算
& 运算符可以直接对二进制进行操作，1 & 1 = 1，1 & 0 =0， 0 & 1 = 0， 0 & 0 = 0，
我们不难发现只有1&1才是1，根据这个思想，我们可以判断当前数字的二进制是否有1
>> 右移运算符，可以删掉末尾二进制数
例如5 的二进制为101 5>>1 ==2 2的二进制为10 删掉了原先末尾的1
再例如6的二进制为110 6>>1==3 3的二进制为11 删掉了末尾的0
其实不难发现，右移1就是乘以2，>>n,就是乘以2^n次方
结合&和>>
我们可以写个循环。逐渐判断每一位是否是1
int b = 13;
int res = 0;//统计b二进制1的数目
while(b){
if(b&1==1)res++; //如果当前位为1，就统计+1
b = b>>1;//将末尾位删掉
}
快速幂思想及实现
快速幂思想其实很简单，就是公式的转换
1、当指数是偶数时，我们可以让指数除以2，底数乘以底数
2、当指数是奇数时，我们可以将指数变为偶数
例如 2^10
指数是偶数，2^10 = 4^5 => (2*2*2*2*2*2*2*2*2*2)=(4*4*4*4*4)
指数是奇数，4^5 = 4 * 4^4
指数是偶数， 4 * 4^4 = 4 * 16^2
指数是偶数，4 * 16^2 = 4 * 256^1
指数是奇数， 4 * 256^1=4 * 256 * 256^0
指数为0时停止，那么答案就是计算 4 * 256 = 1024
代码模拟过程
#include<bits/stdc++.h>//c++万能头文件
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,stack,map,set,vector,queue时都要使用
long long quick_pow(long long a,long long b){//a是底数，b是指数
long long ans=1;//初始化答案为1
while(b){//当指数不为0时执行
if(b%2==0){//指数为偶数时，指数除以2，底数乘以底数
b/=2;
a*=a;
}else{//指数为奇数时，分离指数，ans乘以底数
ans*=a;
b--;
}
}
return ans;//ans就是答案
}
int main(){
long long n,m;
cin>>n>>m;
cout<<quick_pow(n,m)<<endl;
}
快速幂精简模板
#include<bits/stdc++.h>
using namespace std;
long long quick_pow(long long a,long long b){
long long ans=1;
while(b){
if(b&1)ans*=a;
b>>=1;
a*=a;
}
return ans;
}
int main(){
long long n,m;
cin>>n>>m;
cout<<quick_pow(n,m)<<endl;
}
取模版快速幂
上面的快速幂是最原始版的，一般不是很常用，当a本身非常大时，如果a*a可能 long long 都给爆掉了，所以我们一般会采取取模的方式进行运算
前置知识 (a * b * c * d )%p = (((a * b)%p * c)%p * d)% p
即每次乘以下个数前可以先取模，这样最后答案不变，所以我们的代码可以进行优化了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL quick_pow(LL a, LL b, LL p){ //LL是long long 的缩写
//p是要对取模的数字
LL ans = 1;
while(b){
if(b & 1)ans =(ans*a)%p;
b >>= 1;
a = (a*a) % p;
}
return ans;
}
LL mod=10003;
int main(){
long long n,m;
cin>>n>>m;
cout<<quick_pow(n,m,mod)<<endl;
}