说点我们不知道的。

你正在打一个模拟赛。T1 的题面是这样的。

给定 $a,m,T$ ， $T$ 组询问，每次给定 $b$ ，求 $a^b\bmod m$ 。 $a,b,m\le 10^9,T\le 10^8$ 。

这对你来说也太简单了不是吗？

考虑根号分治。设定阈值

B

，预处理出

a^{1\sim B}

和

(a^B)^{1\sim b/B}

即可。作为根号平衡高手，你一眼就看出了

B=\mathcal O(\sqrt b)

时取最优复杂度

\mathcal{O}(\sqrt b)-\mathcal{O}(1)

。

于是你看向 T2：

给定 $a,m,T$ ， $T$ 组询问，每次给定 $b$ ，求 $a^b\bmod m$ 。 $a,b,m\le 10^{18},T\le 10^8$ 。

这不是完蛋了吗！

冷静一下，发现我们可以取

B=\mathcal O(\sqrt[3]b)

，预处理出

a^{1\sim B}

，

(a^B)^{1\sim B}

和

(a^{B^2})^{1\sim b/B^2}

即可。时间复杂度

\mathcal{O}(\sqrt[3]b)-\mathcal{O}(1)

。

然而 T3 是什么呢？

给定 $a,m,T$ ， $T$ 组询问，每次给定 $b$ ，求 $a^b\bmod m$ 。 $a,b,m\le 10^{36},T\le 10^7$ 。

啊？？？？？？

这下取三次根都不太行了。于是你自然而然地选择了六次根。在这个过程中，你惊讶地发现：若你选择了

B=\mathcal{O}(\sqrt[k]b)

，那么你就能做到

\mathcal{O}(kB)-\mathcal{O}(k)

查询。这可太给力了！

不过 T4 立刻给你扇了一巴掌：

给定 $T$ ， $T$ 组询问，每次给定 $a,m,b$ ，求 $a^b\bmod m$ 。 $a,b,m\le 10^{18},T\le 10^6$ 。

坏事了，这下预处理复杂度也乘到

T

上了。不过作为根号平衡大师，你马上就看出了问题的关键点：让预处理和查询的复杂度平衡不就好了吗！于是你选择了

B=\mathcal{O}(\sqrt[\log b]b)

，成功做到了

\mathcal{O}(T\log b)

的复杂度，AK 了这场比赛。

等会啊，这是不是叫快速幂来着。

文章操作