CSP-J/S 算法探秘——多种方式实现快速幂(上)

算法探秘：多种方式实现快速幂（上）

幂运算是在设计算法过程中经常用到的基本运算，但是C++中没有对应的数学运算符表示，因此最基本的方式为：调用cmath库中的pow(x,y)，从而计算x的y次方的值。

使用pow(x,y)函数

pow函数能够计算x的y次幂，其中x为底数，y为指数。但需要注意的是，x、y和pow()函数的返回值都是浮点型，如果写成整型可能会出现下面的问题：

int a=3,b=3;
printf("%d的%d次方为%d\n",a,b,pow(a,b));
float x=3,y=3;
printf("%.1f的%.1f次方为%.2f",x,y,pow(a,b));

由于在printf()中将pow()的格式控制符设置为%d，而pow()函数的返回值为float，因此输出会变为0。如果想要让计算结果为整型，需要用int()函数强制类型转换一下。

如果使用pow()函数来做洛谷平台的这一题：

最终评测结果为：

原因在于题目的数据规模：

由于数据规模过大，a的b次方结果肯定会超过long long类型的最大值，因此需要想别的办法来计算幂运算。

使用循环语句实现幂运算

如果pow()函数会溢出，那么可以回归到循环语句，a的b次方可以看做是b个a相乘，因此可以使用for循环来计算幂运算的值，同时要注意，由于最后的结果要对p取模，那么根据取模运算分配律：

(a * b) % p = ( (a % p) * (b % p) ) % p

每次循环做乘法的时候都进行取模，尽可能地避免答案溢出。参考代码如下：

long long a,b,p;
cin>>a>>b>>p;
long long ans=1;
for(long long i=0;i<b;i++){
  ans=(ans%p)*(a%p)%p;
}
printf("%lld^%lld mod %lld=%lld",a,b,p,ans);

最终评测结果为；

但还是出现了三个评测点TLE，即Time Limit Exceeded程序运行超时。再次看一下数据规模，发现指数b<2^31，2147483648，而时间限制为1s，1s内程序的操作次数最多为10^8次，显然不够用，因此还需要想办法来优化循环，减少次数。

使用递归算法进行快速幂

★★在数学中，幂运算遵循一些运算公式：

（1）同底数幂相乘，底数不变，指数相加

（2）不同底但同指数相乘，指数不变，底数相加

（3）幂的乘方公式，底数不变，指数相乘

在使用递归的快速幂算法中，我们就会用到幂运算的第一个性质，这个性质与分治算法的思想类似，可以将一个大指数的幂运算拆分成两个小指数的幂运算相乘，据此，我们可以写出递推公式：

结合公式，我们就可以写出对应的递归函数代码：

long long kpow(long long a,long long b)
{
  if(b==1){ //递归边界
    return a;
  }
  else{
    long long ans1=kpow(a,b/2)%p;
//这里充分利用C++除法性质，b如果是奇数，b/2与(b-1)/2结果是一样的
    ans1=(ans1*ans1)%p;
    if(b%2==1)ans1=(ans1*a)%p;
    return ans1%p;
  }
}

完整代码的评测结果如下：

通过递归算法，成功让幂运算的时间复杂度从O(b)降低到了O(logb)，从而能够在规定时间内AC了所有测试点。

总结

上述介绍的快速计算幂运算方式，都是使用了数学技巧来对幂运算进行的优化，但是如果能将快速幂与二进制相结合，就可以做到在O(1)的时间复杂度中计算出幂运算的结果，这个算法会在下期进行详细地介绍，敬请期待！！