快速幂

快速幂，是一个在 $\Theta(\log n)$ 的时间内计算 $a^n$ 的小技巧。

对于 $n$ ，它有 $\lceil \log n\rceil$ 个二进制位，那么我们只需要进行 $\log n$ 次的乘法就可以计算出 $a^n$。

例如计算 $4^{12}$，我们将 $12$ 改写为二进制形式：$(1100)_2$，那么 $4^{12}$ 就等于：
$$
4^{12}=4\times 4^{1\times 2^2}\times 4^{0\times 2^1}\times 4^{0\times 2^0}
$$
也就是：
$$
4^{12}=4\times 4^{1\times 2^2}\times 1\times 1
$$
所以最终的答案就只是 $4^{1\times 2^3}$ 与 $4^{1\times 2^2}$ 相乘。而 $4^{23}$ 只需要靠 $4^{22}\times 4$ 来获得即可。由此可以得出思路：进行 $\lceil \log n\rceil$ 次乘 $a$ 的运算，当这一位的 $n$ 为 $1$ 的时候，将答案与此时的 $a$ 相乘即可。

代码如下：

int power(int a,int b){
	int ans=1;
	while(b){
		if(b&1)
			ans=ans*a;
		b>>=1;
		a*=a;
	}
	return ans;
}