基于值域的快速幂新算法

· · 科技·工程

给定 M

Q$ 次询问每次给出$1\le x,y\le V$,求 $x^y \bmod M

以下默认乘法复杂度为O(1)

  1. 光速幂

求a^i 其中a固定

预处理a^0,a^1\dots,a^{B-1} 和 a^B a^{2B} a^{\lfloor \frac{V}{B} \rfloor B}

取B=\sqrt{V}就可以\sqrt{V}预处理，O(1)回答

  1. 拓展

更一般的把指数看成B进制数

快速幂就是$B=2$,光速幂就是$B=\sqrt{V}
  1. n^n

先讲对f(i)=i^i如何线性求 f(1),\dots,f(V)

一个老做法是做 i=pq 的分解，但它的可拓展性太差了

由基于值域预处理的快速 GCD，我们知道

i=abc,a\leq b\leq c,c\leq \sqrt{i}$或者 $c\in Prime i^i=(abc)^{abc}=(a^{abc})\times (b^{abc})\times (c^{abc})

由O(\sqrt{V})-O(1)的光速幂，可以对所有的x\leq \sqrt{V}预处理

时间复杂度O(V)

前两项就可以O(1)求出了

否则$c$为$>\sqrt{V}$的素数 $c^{abc}=(c^c)^{ab}

对每个素数p快速幂求出p^p，这个是线性的

还要预处理出(p^p)^1,(p^p)^2,\dots,(p^p)^{\lfloor \frac{V}{p} \rfloor}

神奇的是这里不用光速幂复杂度也是对的

\sum\limits_{\sqrt{V}<p<V,p \in Prime }\frac{V}{p}=O(V)
  1. 回到原问题

对x^y同样这么做

等价于求p^y

考虑O(B\frac{\ln V}{\ln B}) - O(\frac{\ln V}{\ln B})的做法

直接暴力每个的素数这样干一下

时间复杂度O(V\frac{B}{\ln B}+Q\frac{\ln V}{\ln B})

当V,Q同阶时，B=\ln V

总复杂度O(\frac{V\ln V}{\ln {\ln V}})

  1. 动态平衡

上个做法太无脑暴力了

考虑离线,对每个p平衡下它的B

$B\frac{\ln V}{\ln B}+q\frac{\ln V}{\ln B}

取B=q

时间复杂度q\frac{\ln V}{\ln q}

注意到这个东西在q不平衡分布时时间复杂度反而会小

显然对刻意构造的询问这么做没用

假定 x,y 随机生成

此时q在p.\sqrt{V}<p\leq V上的分布与\frac{1}{p}成正比

可以证明此时时间复杂度为O(V\ln\ln V)

作为习题留给读者

  1. 基于模数
M=p_{1}^{\alpha_{1}}\times \dots \times p_{k}^{\alpha_{k}}

分解之后做CRT合并

有原根g时

x^y=g^{y\log_g{x}}

光速幂的形式，只要求\log_g(x)即可

基于值域预处理的快速离散对数

对2^l情况

x$偶数,答案不为$0$时$y<l

暴力\ln l=\ln\ln M

x$奇数可表示成$(-1)^a5^b

同理BSGS搞出来a,b

直接做5的光速幂就行了

模数随机

(Q+V)\ln \ln M+\frac{M^{3/4}}{\sqrt{\ln M}}\ln \ln M

模数不随机

(Q+V)\frac{\ln M}{(\ln \ln M)^2}+\frac{M^{3/4}\sqrt{\ln M}}{(\ln \ln M)^2}