快速幂
引入：
求 $a^b\bmod p(1\leq a,b,p\leq 10^9)$。
$a^{2b}=(a^b)^2$，所以若 $b$ 是 $2$ 的一个整数幂，那就容易了，因为一定可以变型成 $a^{2^{2^{2^·}}}$ 的形式，每次只要计算一个新的平方即可，总共只要计算 $O(\log b)$ 次即可。
若 $b$ 不是 $2$ 的一个整数幂，其实也不复杂，只要把 $b$ 拆成 $\frac{b-1}{2}$ 和 $\frac{b+1}2$ 即可。对 $\frac{b-1}2$ 和 $\frac{b+1}2$ 同样递归即可。可以证明，最后出现的不同数字为 $O(\log b)$ 级别的。
但是仅仅递归的话，可能还需要记忆化。所以一般会写成递推（迭代的形式）。或是以下二进制指数的等价表示。
$a^b=a^{b(2)}$，$b(2)$ 为 $b$ 的二进制表达。
$a^b=\prod a^{p_i}$，其中 $p_i=2^i$，满足 $p_i$ 是 $b(2)$ 中的 $1$ 位。
此时，就只需要计算 $a$ 的 $2$ 的整数幂次即可。可以预处理后按照 $b$ 的二进制表达计算即可。
时间复杂度：$O(\log b)$。
X 进制快速幂：
通常使用的快速幂为二进制快速幂，即把 $b$ 视作一个二进制数后去考虑计算。
但是其本质是按位算贡献，所以同样可以扩展到 $X$ 进制快速幂。
$a^b=\prod a^{A_i\times p_i}$，其中 $p_i=X^i$，$A_i$ 是系数，因为二进制只有 $0/1$，但是 $X$ 进制有 $[0,X-1]$。
所以预处理就不能只处理 $a$ 的 $X$ 的整数次幂了。共需要 $O(X\log_X^b)$ 的预处理。
因此 $X$ 进制快速幂的时间复杂度为：$O(X\log_X^b)$（容易发现二进制快速也符合这个式子）
X 进制的一个优势也在于，若题目给出的数是一个较大的整数（不能用整型变量存储 $b$，则可以直接按位算贡献）
光速幂：
若多次询问 $a^b\bmod p$，但是底数 $a$ 是相同的，可以通过 $O(\sqrt b)$ 预处理，做到 $O(1)$ 处理单次询问。
本质是一种大步小步算法。
考虑一个整数 $b$ 一定可以写成 $x\sqrt{b_{max}}+y$ 的形式，其中 $x,y\leq \sqrt{b_{max}}$。得到 $x,y$ 的方式也简单，$x=\lfloor\frac{b}{\sqrt{b_{max}}}\rfloor,y=b\bmod \sqrt{b_{max}}$。
所以预处理 $a^{0},…,a^{\sqrt{b_{max}}-1}\bmod p$ 的值，再预处理 $a^{\sqrt{b_{max}}},…,a^{\sqrt{b_{max}}\times\sqrt{b_{max}}}$ 的值。询问的时候做一次乘法即可。
时间复杂度：$O(\sqrt{b_{max}})$。
龟速乘：
龟速乘用于解决模数较大的情况。
例如：求 $a\times b\bmod p(1\leq a,b,p\leq 10^{18})$。
最后的结果一定 $\leq 10^{18}$，但是乘的过程超过了 $10^{18}$。
不能计算出结果后再取模。
解 1：
转成 long double，再把取模变成带余除法。
有精度问题。
解 2：
将乘法变成加法。$b+b$ 并没有超过 long long，考虑 $a$ 的二进制表达，原式可变型为 $\sum 2^i\times b$，这个 $2$ 的整数幂同样累积预处理即可。每次只需要对一个 $10^{18}$ 的数做一个乘 $2$ 即可。