快速幂问题

快速幂就是快速算底数的a^n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

以a^10为例。我们知道，求一个数的平方是很快的，因为不用循环。那么a^10能不能转化为谁的平方？没问题，a^10是a^5的平方，也就是说，如果a^5求出来了，那么接下来只需对这个结果平方就能得出结果，并且少做了4次乘法（求平方本身需要一次乘法）！

a^5能不能用类似的方法求出来？按照刚才的思想，指数应该能被2整除。我们可以先求a^4，然后再乘一个a就是a^5。很明显，a^4是a^2的平方，而a^2可以直接求出来。于是我们最终只做了4次乘法。

总结刚才的思路，则有

                                n是零

                n是偶数

          n是奇数

程序设计原理

以下以求a的b次方来介绍

把b转换成二进制数。

该二进制数第i位的权为  

例如：

11的二进制是1011  

因此，我们将a¹¹转化为算：

快速幂可以用位运算来实现

1. b & 1//取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶
2. b>>1//把b的二进制右移一位，即去掉其二进制位的最低位

快速幂完整代码

1. #include<cstdio>
2. long long quickpower(long long a,long long n) {
3.  long long ans=1,cnt=a;
4.  while(n){
5.    if(n&1){ans*=cnt;}
6.    cnt*=cnt;
7.    n>>=1;
8.  }
9.  return ans;
10. }
11. int main()
12. {
13.   long long a,n,ans;
14.   scanf("%lld %lld",&a,&n);
15.   ans=quickpower(a,n);
16.   printf("%lld",ans);
17.   return 0;
18. }