快速幂

快速幂算法能帮我们算出指数非常大的幂，传统的求幂算法在指数n非常大的时候，时间复杂度会非常高。

快速幂算法的核心思想就是每一步都把指数分成两半，二相应的底数做平方运算。这样指数会不断变小，从而所需要执行的循环次数也变小。

模板

typedef long long LL;
int qmi(int a, int b, int p) {	// a为底数，b为指数，p为模值
	int res = 1 % p;	// p=1时，任何数模1都为0
	while (b) {
		if (b & 1)	res = (LL)res * a % p;
		b >>= 1;
		a = (LL)a * a % p;
	}
    return res;
}