前言
题目传送门 Luogu P1405 苦恼的小明
题意
求 \(a_1^{a_2^{\cdots^{a_n}}}\) 对 \(10007\) 取余的结果。\(n\le 1234567\) 。
思路
看到一百万层的幂塔，立刻能想到扩展欧拉定理。这个东西可以大大降低指数的大小。
我们用扩展欧拉定理对这个幂塔进行化简：
\[\begin{aligned}
a_{1}^{a_2^{a_{3}^{\cdots^{a_{n}}}}}\equiv
a_{1}^ {a_2^{a_3^{\cdots^{a_n}\mathrm{~mod~}\varphi(\varphi(\cdots\varphi(p)))+\varphi(\varphi(\cdots\varphi(p)))}
\mathrm{~mod~}\varphi(\varphi(p))+\varphi(\varphi(p))}
\mathrm{~mod~}\varphi(p)+\varphi(p)}\ (\ \bmod p\ )
\end{aligned}
\]
（最后一个 \(\bmod p\) 是同余的模，不在指数中哦）
呃。。。真的有在化简吗(?
不管怎么说，现在指数虽然变长了，但值也变小了。而且这个式子长成一个非常典型的递归结构，我们不难看出可以从第一层开始逐层向上爬，求出幂塔的每一层指数，根据扩展欧拉定理，设这一层取模的模数是 \(m_i\) ，如果它 \(\ge \varphi(m_i)\) 就进行取模再加，否则不变。然后我们在回溯的过程中逐层用快速幂求得最后答案即可。
还容易观察到，这个不断嵌套的 \(\varphi(p)\) 在至多十四轮嵌套之后就会变成 \(1\) ，而任何数模 \(1\) 都得 \(0\) ，所以在递归过程中，我们若发现 \(m_i=1\) ，就可以直接返回了。
还需要注意到，每一层幂塔的指数与 \(\varphi(m_i)\) 的大小关系决定了要不要取模，而这个指数就是上一层递归的答案，\(\varphi(m_i)\) 就是上一层递归的模数。所以我们递归不仅要返回当前的答案，还要返回当前层答案与模数的大小关系，以供后续层使用。
代码
由于式子实在繁琐，可能有文字无法叙述清楚的地方，可结合代码更好理解。
#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define pib pair<int, bool>
#define mkp(a, b) make_pair((a), (b))
#define MIKU 0
using namespace std;const int MOD = 10007;int n, a[1234570];
int ans = 1;int qpow(int a, int n, int m) { //普通的快速幂int ans = 1;a %= m;while(n > 0) {if(n & 1) ans = ans * a % m;a = a * a % m;n >>= 1;}return ans;
}int phi(int a) { //普通的求欧拉函数int ans = a;for(int i=2; i*i<=a; i++) {if(a % i == 0) {while(a % i == 0) a /= i;ans = ans / i * (i - 1);}}if(a > 1) ans = ans / a * (a - 1);return ans;
}pib calc(int k, int m) { //需要两个返回值if(k == n) return {a[k], a[k] >= phi(m)}; //最后一层没有指数，直接返回，同时返回大小关系if(m == 1) return {0, 1}; //如果模数减到一，说明后面还有多层幂塔，一定是大于模数的，大小关系为 true 。int ans = a[k], pm = phi(m);auto [pw, f] = calc(k+1, pm); //pw:指数 f:指数与 φ(m) 的大小关系return f ? mkp(qpow(ans, (pw % pm) + pm, m), true) : mkp(qpow(ans, pw, m), pw > pm); //按照大小关系决定要不要对指数取模，同时把本层的大小关系传递给下层。如果取了模，因为又加了模数，所以一定是大于。
}signed main() {fastio;cin>>n;for(int i=1; i<=n; i++) cin>>a[i];int ans = calc(1, MOD).first;cout<<ans;return 0;
}