【分治】----快速幂
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.分治法求快速幂
在平常中我们如果遇到求
现在我们如果要求
根据前面幂的运算法则，可以得出2^11=2^5 * 2^5 * 2^1 。 2^5=2^2 * 2^2 *2^1 。 2^2=2^1 * 2^1
再例如：现在我们如果要求 216的值，那么就要计算 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是偶数，只需要每次乘
，然后将次方b缩减一半即可。如果次方b是个奇数，可以先将这个a自乘一次，这样剩余的b-1次方就是偶数了。
快速幂是一个将底数等价增大，指数等价缩小的过程。总结：b是偶数：
b是奇数:
我们用res表示结果；那么求ab的过程代码描述如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #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; } |
求
4.递归法求快速幂
5.迭代法求快速幂
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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
