快速幂的基本原理是简单的：欲计算 $a^b$ 的值，只需计算 $a^{b/2}$ 的值即可。

在数论题当中，时常涉及到乘法的取模运算。这里用到一个原理：

$$(a\times b)\,\bmod p= [(a\,\bmod p)\times(b\,\bmod p)]\,\bmod p $$

int solve(int a,int b){
	if(b==0) return 1;
	if(b==1) return a%p;
	if(b%2==0){
		int tmp = solve(a,b>>1); //必须预存tmp的值，否则程序的效率与普通乘幂无异
		return (tmp*tmp)%p;
	}else{
		int tmp = solve(a,b>>1);
		return (tmp*tmp*(solve(a,1))%p)%p;
	}
}