Luogu P1405 苦恼的小明 题解

前言

题目传送门 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;
}