[数据结构与算法]快速幂 || 取余运算

首先，我们需要知道，在求一些比较高的幂时

往往C++的最大数据类型（unsigned long long?类型）是不够用的

写题时可能还会出现 MLE?的现象

对于此类现象?快速幂 || 取余运算?是个不错的选择。

代码如下：

int qpow(int a, int n, int p){ // 定义qpow()函数
	int ans = 1; // 定义初始化ans
	while(n){ // 判断只要n不等于0就一直循环
		if(n % 2){ // 当n的二进制表达数的最后一位是1时，执行
			ans = (ans * a) % p; 
            // 将ans与a相乘再取模（相当于让n的二进制的各个数位上的数字乘以位数在相加）
		}
		n /= 2; // 让n的二进制位数从后往前依次递减
		a = (a * a) % p; // 求出所在数位
	}
	return ans; // 返回ans
}