1.幂
幂（power）是指乘方运算的结果。n^m指该式意义为m个n相乘。把n^m看作乘方的结果，叫做n的m次幂，也叫n的m次方。
2.幂的数学表示和规则
$2^3 * 2^4=2^7$
$3^4 * 3^4=3^8$
3.分治法求快速幂
在平常中我们如果遇到求 $a^b$ 的时候，可能是一个一个挨个乘起来，也就是将a乘b次，如果b的值非常大时，在算法竞赛中又有时间限制，累次乘几乎是不行的。（不要说这个时候用pow() 函数）例如：$2^{1000}$ ，用循环累次乘的话需要1000次。
现在我们如果要求 $2^{11}$ 的值，那么就要计算 $2*2*2*2*2*2*2*2*2*2*2$
根据前面幂的运算法则，可以得出$2^{11}$=$2^5$ * $2^5$ *$2^1$ $2^5$=$2^2$ * $2^2$ *$2^1$ $2^2$=$2^1$ * $2^1$
再例如：现在我们如果要求 $2^{16}$ 的值，那么就要计算 16个2相乘。根据前面幂的运算法则，可以得出$2^{16}$=$2^8$ * $2^8$ $2^8$=$2^4$ * $2^4$$2^4$=$2^2$ * $2^2$$2^2$=$2^1$ * $2^1$
从上面两个例子可以看出，如果用类似于次方一半的方式进行累乘，那么需要计算的次数可以减少很多。这就是分治法求快速幂的核心。
再来找一下分治法求快速幂的规律。可以看出上面两个的主要区别在于次方是奇数还是偶数，如果是次方b是偶数，只需要每次乘$a ^ {\frac{b}{2}}$ ，然后将次方b缩减一半即可。如果次方b是个奇数，可以先将这个a自乘一次，这样剩余的b-1次方就是偶数了。
快速幂是一个将底数等价增大，指数等价缩小的过程。总结：b是偶数： $a^b$ = $(a^2)^\frac{b}{2}$ b是奇数：$a^b$ = $a*(a^2)^\frac{b}{2}$ 或 $a^b$ = $a*(a^2)^\frac{b-1}{2}$我们用res表示结果；那么求$a^b$的过程代码描述如下：
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int a,b,res=1; //定义底数，次数，结果
cin>>a>>b;
while(b!=0) //次方减半不到0时继续
{
if(b%2==1) //如果b是奇数,(最后一次一定是奇数)
res=res*a; // 先乘自己一次，这样就能一半是偶数
a=a*a; // a^2 ,a^4, a^8 ...
b=b/2; // 这个地方如果是b>>=1 速度更快 ,缩减一半工作量
}
cout<<res<<endl;
return 0;
}
根据代码稍微模拟一下上面的过程，计算$2^{11}$,
- 第一次循环, b =11 ,这个时候可以将$2^{11}$,分成$2^1$ * $(2^2)^5$, 那么下几层的总目标是让res=$(2^2)^5$。也就是要计算$4^5$。
- 第二次循环，因为b为5是奇数，$4^{5}$,分成$4^1$ * $(4^2)^2$, 那么下几层的总目标是$(4^2)^2$，也就让res=${16}^2$,
- 第三次循环，b是偶数，只需要把${16}^2$当成$({16}^2)^1$即可，下几层的总目标是计算$({16}^2)^1$
- 第四次循环，是奇数，这个时候已经不用看循环了，直接计算res=res*a就可以完成计算了。
| 循环 | while(b!=0) | if(b%2==1) | res=res*a | a=a*a | b=b/2 |
| 1 | b=11,成立 | b=11,成立 | 2 | 2*2=$2^2$ | 5 |
| 2 | b=5,成立 | b=5,成立 | 2*$2^2$ | $2^2$*$2^2$=$2^4$ | 2 |
| 3 | b=2，成立 | b=2,不成立 | $2^4$*$2^4$=$2^8$ | 1 | |
| 4 | b=1，成立 | b=1，成立 | 2*$2^2$*$2^8$ | $2^8$*$2^8$=$2^{16}$ | 0 |
| 5 | b=0，不成立 |
求$3^{11}$的动图演示。
4.递归法求快速幂
#include<cstdio>
int pow_mod(int a ,int n) {
if(n == 0)
return 1;
int x = pow_mod(a,n / 2);
long long ans = (long long)x * x ;
if(n%2 == 1)
ans = ans *a ;
return (int)ans;
}
int main() {
int a,b;
scanf("%d%d",&a,&b);
printf("%d",pow_mod(a,b));
return 0;
}
5.迭代法求快速幂
#include<bits/stdc++.h>
using namespace std;
long long pow_d(long a,long b){
long ans=1;
while(b>0){
if(b&1){//如果b的二进制末尾为1 ，就相当于被选中了。
//就如2^13 ==> 2^(13==>1101)==> 2^(1101) ==> 3 2 0 号为 1 那么被选中 ==> 2^13 = 2^8 * 2^4 * 2^1
ans=ans*a;//令ans累积上a
}
a=a*a;//令a平方
b>>=1;//将b的二进制右移一位即
}
return ans;
}
int main(){
long long a,b;
cin>>a>>b;
long long result=pow_d(a,b);
cout<<result<<endl;
return 0;
}
6.快速幂中中的取余运算
搜索快速幂的时候经常发现最后有个取余运算，主要原因是因为现在oj网站的题或者竞赛的题，如果a的b次幂且b很大，那么题中大多会让你把结果对一个数取余也就是求模，例如a^b%c这种。
介绍一个公式:
(a*b)%m = (a%m * b%m) %m
所以在一些求快速幂中会出现取余现象。
例题
【题目描述】假设今天是星期日，那么过 a^b天之后是星期几？
【输入描述】两个正整数 a，b，中间用单个空格隔开。100000<a≤100,0<b≤10000。
【输出描述】一个字符串，代表过 a^b 天之后是星期几。
其中，Monday 是星期一，Tuesday 是星期二，Wednesday 是星期三，Thursday 是星期四，Friday 是星期五，Saturday 是星期六，Sunday 是星期日。
【样例输入】3 2000
【样例输出】Tuesday
【分析】上面这道题目出现了2000次方，比较大所以考虑到取余的问题，实际上我们只有按照题目要求，每次运算求幂的时候对7取余即可。类似下面这样：
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
int a,b,res=1,m=7; //定义底数，次数，结果,取余
cin>>a>>b;
while(b!=0)
{
if(b%2==1) //如果b是奇数,(最后一次一定是奇数)
res=res*a%m;
a=a*a%m;
b=b/2;
}
cout<<res<<endl;
return 0;
}
返回目录：算法