青少年编程知识记录 - 【分治】----快速幂

2021年01月28日 16:01:08

【分治】----快速幂

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() 函数）例如：21000，用循环累次乘的话需要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

再例如：现在我们如果要求 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是偶数，只需要每次乘ab/2

，然后将次方b缩减一半即可。如果次方b是个奇数，可以先将这个a自乘一次，这样剩余的b-1次方就是偶数了。

快速幂是一个将底数等价增大，指数等价缩小的过程。总结：b是偶数： b是奇数:

$a^{b}$ 我们用res表示结果；那么求ab的过程代码描述如下：

#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; 
} 

求311的动图演示。

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;   }