快速幂
为什么要用快速幂
计算\(a^b\space mod\space p\)，其中\(a,b\)是非常大的数。这时如果将\(a^b\)一个一个累乘计算的话会很慢，即使他的时间复杂度是\(O(n)\)，并且这样一个大的数字很难存储在计算机中(\(int,long long\)都会溢出)，这时就需要快速幂来解决这个问题。
在\(RSA\)加密中就使用了快速幂算法
原理
快速幂其实就是利用了分治的思想，将 \(a^b\) 分成 \(a^{b/2}\) 和 \(a^{b/2}\) 两个部分，一直细分，直到幂次 \(b=1\) ，再将这些结果累乘起来，并且利用模运算的性质，在累乘过程中不断取模，防止溢出，最后就可以得到最后的答案。
递归实现
递归的思路非常简单，常规套路。
typedef unsigned long long ull;
ull a, n, p;
ull q_pow(ull a, ull n,ull p) {
if (n == 1) return a;
ull c = q_pow(a, n >> 1, p) % p;
if (n & 1) return c * c % p * a % p;
return c * c % p;
}
非递归实现
非递归需要利用到二进制。对于任意一个数字我们都可以把它写成二进制累加的形式，\(e.g.5=2^2+2^0\)，所以，我们就可以把幂\(b\)写成一个二进制累加的形式，再利用幂的运算规则，就可以将\(a\)写成一串数的乘积，\(e.g：3^5=3^{2^2+2^0}=3^{2^2}\times 3^{2^0}\)，这样也达到了将幂次二分的效果，并且我可以直接将幂次写成二进制的形式\(3^{(101)_2}\)，每个二进制位为\(1\)的位置，都是我们要累乘的幂次。
写代码时，我们就可以遍历幂次\(b\)的二进制位，等于\(1\)的就将其乘起来，并且不断取模保证不溢出，最后遍历完\(b\)的二进制位，循环结束，得到的乘积就是结果。