快速幂问题

快速幂就是快速算底数的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¹¹转化为算：

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

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

快速幂完整代码

#include<cstdio>
long long quickpower(long long a,long long n) {
	long long ans=1,cnt=a;
	while(n){
		if(n&1){ans*=cnt;}
		cnt*=cnt;
		n>>=1;
	}
	return ans;
}
int main()
{
	long long a,n,ans;
	scanf("%lld %lld",&a,&n);
	ans=quickpower(a,n);
	printf("%lld",ans);
	return 0;
}