题解：P1226 【模板】快速幂

· · 题解

我们定义 a^b 为 b 个 a 相乘，即 a^b = \underbrace{a \times a \times \cdots \times a}_{b \text{ 次}}。

幂满足以下性质：

a^m\times a^n=a^{m+n} \dfrac{a^m}{a^n}=a^{m-n}

那么接下来我们考虑求 a^b \bmod p，其中 b\le 10^9。

显然直接 \mathcal{O(b)} 乘是不行的，考虑利用上面的性质，将 b 拆成 \mathcal{O}(\log b) 个数的和，然后直接乘即可。

考虑将 b 二进制分解，每次 a 自己乘自己，如果说 b 在二进制的这一位是 1 就乘上 a，这样复杂度是 \mathcal{O}(\log b) 的。

比如说，当 a=3,b=6,p=10^9 时：

维护一个答案 q，初始时 q=1。

观察到 b 二进制最后一位不是 1，直接将 a 自乘，此时 a=9,b=3,q=1。

此时 b 二进制最后一位是 1，答案先乘 a，然后将 a 自乘，此时 a=81,b=1,q=9。

最后 b 的二进制还是 1，答案先乘 a，然后将 a 自乘，此时 a=6561,b=0,q=729。

当某些时候快速幂也不管用时，考虑维护一个 \mathcal{O}(1) 的快速幂。

光速幂是指在底数和模数确定时，可以做到 \mathcal{O}(\sqrt w) 预处理，\mathcal{O}(1) 查询的快速幂，w 为指数的范围。

考虑类似于根号分治的思想，如果我们处理出以 1,2,\cdots B 为指数的答案，以及 1,2,\cdots n 中所有 B 的倍数的答案，那么 \forall i\in [1,n]，2^i 都可以利用这两组数据的乘积得出。

复杂度为 \mathcal{O}(B+\dfrac{n}{B})，显然 B=\sqrt n 时复杂度最优。

LOJ #162 CODE