快速幂
模板
原理
\[
\begin{align*}
&a^b\\
=&\prod_{i=0}^{\log b}{(a^{2^i})^{[b \text{ and } 2^i]}}\\
=&\prod_{i=0}^{\log b}{[b \text{ and } 2^i]?(a^{2^i}):1}
\end{align*}
\]
我们可以在循环的时候通过每次平方并取模的方式持续维护 \(a^{2^{i}}\),这样既可以避免 \(2^{i}\) 太大,也能在很大程度上优化时间复杂度。
高精十进制快速幂
有时,快速幂的指数是一个十进制的高精度字符串。我们希望求出幂对 \(mod\) 取模的结果,可以考虑使用十进制快速幂解决。
\[
a^b=\prod_{i=0}^{\lg b}{(a^{b[i]\times 10^i})}=\prod_{i=0}^{\lg b}{({a^{10^i}})^{b[i]}}
\]
由于 \(b\) 在十进制下的任意一位数字都很小,求出 \(a^{b[i]}\) 的时间复杂度可看作一个常数;我们可以像普通快速幂一样持续维护 \(a^{10^i}\) 取模的结果,并在第 \(i\) 位时对 res
产生 \(({a^{10^i}})^{b[i]}\) 的贡献。