Solution - P4139 上帝与集合的正确用法

P4139 上帝与集合的正确用法

idea:

扩展欧拉定理（降幂公式）与递归。

解法：

题目可以简化为：求 $2^{2^{2^{...}}}\mod p$ 。

不妨令 $x = 2^{2^{2^{...}}}$ ，那么需要求 $x\mod p$ 。

有降幂公式： $a^b\mod p = a^{b\mod \varphi(p)+\varphi(p)}\mod p\ \ \ \ \ \ \ \ (b\geq \varphi(p))$ 。

那么有：

$$x\mod p= 2^x\mod p = 2^{x\mod \varphi(p)+\varphi(p)}\mod p$$

令 $f_p$ 表示 $x\mod p$ 。则有

$$f_p = 2^{f_{\varphi(p)}+\varphi(p)}\mod p$$

这个是可以递归的。边界为 $f_1 = 1$ 。

空间复杂度 $O(n)$ ，时间复杂度 $O(能过)$