欧拉降幂

Grisses · 2024-11-26 21:51:36 · 算法·理论

喵喵喵~

众所周知： a^b \equiv\begin{cases}a^b & b<\varphi(m)\\a^{b\bmod \varphi(m)+\varphi(m) } & b\ge\varphi(m)\end{cases}\pmod m。

同时，当 n>2 时，有 2\mid\varphi(n) 以及 \varphi(2^kn)=2^{k-1}\varphi(n)\le\dfrac{\varphi(n)}2(2\nmid n)。所以易得对 n 求 \log 次 \varphi 后其值固定为 1。

所以对于一个幂塔 a_1^{a_2^{a_3^{\cdots^{a_n}}}}\bmod p，可以考虑递归求 a_2^{a_3^{\cdots^{a_n}}}\bmod\varphi(p)，再据情况考虑是否加 \varphi(p)。容易发现，最多递归 \log 次，这是一件很棒的事。

下面有 3 道例题。

CF906D Power Tower

[Ynoi2016] 炸脖龙 I

上帝与集合的正确用法

给定 n 个数 w_1,w_2,...,w_n 与模数 m。

给出 q 组询问，每次询问给出 l,r，求 w_l^{w_{l+1}^{{...}^{w_r}}} \mod m 的值。

考虑对于一次询问 S(l,r,m) 规约到 S(l+1,r,\varphi(m))，做完了。

上帝与集合由于指数一直是 2 的无穷幂塔，所以一定会加上 \varphi(m)。另外两题注意在快速幂时打个标记记录是否取过模。