快速幂

示例

1. $x^{20}$
2. $\begin{align}20=&(10100)_2\=&02^0+02^1+12^2+02^3+1*2^4\=&0+0+4+0+16\end{align}$
3. $x^{20}=x^0x^0x^4x^0x^{16}$
4. 每前进一位，x就要平方一次

代码实现

//基础版，用处不大（既然需要快速幂了int大概是不够的）
//可以把 函数、x、result 改为long long型
int QuickPow(int x,int a){
	int result = 1;
	while(a){
		if(a%2==1) result *= x;
		x *= x;
		a /= 2;
	}
	return result;
}
//带取模的快速幂
int mod = 17001;
int QuickPow(int x,int a){
	int result = 1;
	while(a){
		if(a%2==1) result *= x;
		x *= x;
		a /= 2;
		x %= mod;
		result %= mod;
	}
	return result;
}