快速幂

· · 个人记录

测试题目。不保证是最优解。认为 n=\Omega(p^{\epsilon}) 即 \log n 与 \log p 同阶。

不难发现幂这个东西没什么好的性质，于是我们需要对问题进行适当转换。考虑浮点数 pow 之所以能做到 O(1)，本质是先算 ln 再做乘法再 exp。那这里我们可以考虑差不多的思路，对于 x^y 且 x\not=0，将其转化为 g^{y\log_gx}，其中 g 为模 p 意义下的原根即 3。外层启动光速幂，于是我们现在只需要对 \forall 1\le x\le n 求出 y 满足 g^y\equiv x\pmod p。不难发现这个东西可以欧拉筛，于是我们现在只需要对每个素数求出这玩意即可。换而言之，我们现在需要一个 O(\log p) 的算法求出给定数 x 的离散对数。

我们考虑 p-1=2^{23}\times119，不妨将这部分分开考虑。不难发现 (g^{2^{23}})^y\equiv x^{2^{23}}\pmod p 且 g^{2^{23}} 阶为 119，换而言之我们令 x'=x^{2^{23}}，g'=g^{2^{23}}，则解方程 g'^{y'}\equiv x'\pmod p 即可得出 y 模 119 的值。这部分比较简单，我们把 119 个值全部预处理到 map 里用的时候查表完事，或者细化一点就存数组做二分。我们考虑如法炮制，解 (g^{119})^y\equiv x^{119}\pmod p 以得到 y 模 2^{23} 的余数，然后 CRT 合并即可。不难发现这次我们没法打表了。就算时间可以，空间也开不下。

考虑对 x 逐位确定。对于 0\le r\lt 23，记 y=a\times2^{r+1}+b\times2^r+c，换句话说就是把二进制在 r 这一位前后与本体裂成三段。我们现在要做的是，已知 c，把 b\times2^r+c 求出来，有了这个事情之后就能从小到大完成确定了。注意到 x^\frac{p-1}{2^{r+1}}\equiv g^{a(p-1)+b\times\frac{p-1}2+c\times\frac{p-1}{2^{r+1}}}\equiv g^{b\times\frac{p-1}2+c\times\frac{p-1}{2^{r+1}}}，也就是说我们只需要比对 x^\frac{p-1}{2^{r+1}} 与 g^{c\times\frac{p-1}{2^{r+1}}} 是否相等即可快速得出 b 是否为 0。后者我们可以复用一下我们的光速幂，而前者可以把全部 23 个值写递推存起来。于是我们完成了这个流程。

以上。复杂度 O(n)-O(1)。后来查阅了资料，这个叫 Pohlig–Hellman algorithm。