说点我们不知道的。

· · 休闲·娱乐

你正在打一个模拟赛。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 了这场比赛。

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