P1405 苦恼的小明 题解
August_Light
·
·
题解
P1405 苦恼的小明 题解
题目传送门
题意简述
给定长度为 n 的自然数序列 a，求 a_1^{a_2^{\dots^{a_n}}} \bmod 10007。
## 前置知识
[扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)：
$$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$$
## 解法
有了扩展欧拉定理，我们自然会有一个思路：
设 $f(x)$ 为后 $x$ 项形成的幂塔的值。
$$f(x) \equiv \begin{cases} a_x^{f(x+1)} & f(x+1) < \varphi(m) \\ a_x^{f(x+1) \bmod \varphi(m) + \varphi(m)} & f(x+1) \ge \varphi(m) \end{cases} \pmod m$$
根据这个式子，发现事实上我们并不需要真的求出 $f(x+1)$ 的值，我们只需要知道 $f(x+1) \bmod \varphi(m)$ 以及 $f(x+1)$ 和 $\varphi(m)$ 的大小关系。
坑点：有的人求出了 $b$ 对 $\varphi(m)$ 取模的值，然后和 $\varphi(m)$ 比大小，这显然是没有意义且不符合扩展欧拉定理式子的。这个地方杀了一大车题解：[hack](https://www.luogu.com.cn/discuss/655151)。
## 代码
因为 $\varphi$ 的特性，所以递归层数是 $\log$ 级别的，不会超时。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef __int128 int128;
LL phi(LL n) {
LL ret = n;
for (LL i = 2; i * i <= n; i++) {
if (n % i == 0) {
ret = ret / i * (i - 1);
while (n % i == 0)
n /= i;
}
}
if (n != 1)
ret = ret / n * (n - 1);
return ret;
}
int128 qpow(int128 a, int128 b, int128 p) { // 在快速幂的同时保住 a^b 和 p 的大小关系
int128 ret = 1;
while (b) {
if (b & 1) {
ret *= a; if (ret >= p) ret = ret % p + p;
}
a *= a; if (a >= p) a = a % p + p;
b >>= 1;
}
return ret;
}
const int MAXN = 1234567 + 5;
int n;
LL a[MAXN];
LL f(int i, LL p) {
if (i == n+1 || p == 1)
return 1;
return qpow(a[i], f(i+1, phi(p)), p);
}
const int MOD = 10007;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
LL ans = f(1, MOD);
printf("%d\n", ans % MOD);
return 0;
}
```
## 练习题
[POWTOW - Power Tower City](https://www.luogu.com.cn/problem/SP10050)