利用欧拉定理求解指数塔取模运算
题目来源：CSU 2021
问题描述
题目定义了一种称为"exponial"的运算，对于正整数 n，其形式为：
exponial(n) = n ^ ( (n-1) ^ ( (n-2) ^ ( ... ^ (2 ^ 1) ... ) ) )
这里指数运算是右结合的，即 a^b^c = a^(b^c)。例如 exponial(3) = 3^(2^1) = 3^2 = 9。当 n 增大时，该值增长极快。
给定 n (1 ≤ n ≤ 10⁹) 和 m (1 ≤ m ≤ 10⁹)，需要计算 exponial(n) mod m 的值。
核心思路
面对这种超高次幂的模运算，直接计算是不可能的。我们需要借助数论中的指数循环定理（欧拉定理的推广）。核心公式如下：
当 B 足够大时（通常 B ≥ φ(C)），有：
A^B mod C = A^( B mod φ(C) + φ(C) ) mod C
其中 φ(C) 是欧拉函数，表示小于 C 且与 C 互质的正整数的个数。这个公式允许我们递归地降低指数规模。
对于 exponial(n) 问题，我们可以递归应用该定理：
- 如果 m == 1，结果为 0（任何数模1都是0）
- 对于小的 n 值（n ≤ 4），可以直接返回已知结果，避免复杂计算
- 对于一般的 n，利用公式递推：
exponial(n) mod m = n^(exponial(n-1) mod φ(m) + φ(m)) mod m
下面递归关系图展示了算法流程：
代码实现
实现中需要注意几个关键点：
- 使用 long long 类型避免溢出
- 递归深度不会太大，因为每次 m 都会快速缩小
- 底数和指数在快速幂运算中都要取模
#include <cstdio>
#include <algorithm>
typedef long long ll;
// 计算欧拉函数 φ(n)
ll phi(ll n) {
ll result = n;
for (ll i = 2; i * i <= n; ++i) {
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
result -= result / i;
}
}
if (n > 1) {
result -= result / n;
}
return result;
}
// 快速幂：计算 (base^exp) mod mod
ll quickPow(ll base, ll exp, ll mod) {
ll ans = 1 % mod;
while (exp > 0) {
if (exp & 1) {
ans = (ans * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return ans;
}
// 递归计算 exponial(n) mod m
ll solve(ll n, ll m) {
if (m == 1) return 0;
if (n == 1) return 1 % m;
if (n == 2) return 2 % m;
if (n == 3) return 9 % m;
if (n == 4) return (1LL << 18) % m; // 4^(3^2) = 4^9 = 262144
ll pm = phi(m);
ll exp = solve(n - 1, pm); // 递归计算指数部分
// 应用指数循环定理
return quickPow(n % m, exp + pm, m);
}
int main() {
ll n, m;
while (scanf("%lld%lld", &n, &m) == 2) {
printf("%lld\n", solve(n, m));
}
return 0;
}
样例验证
输入：
2 42 5 123456789 94 265
输出：
2 16317634 39
算法要点总结
- 欧拉函数递归降幂：通过递归计算每一层的模数，利用 φ(m) 快速缩小模数规模
- 边界条件处理：n ≤ 4 时的直接返回值避免了不必要的递归深度
- 指数循环定理应用：需要保证指数 ≥ φ(m) 时才能直接使用公式，但本题中很快满足此条件
- 模乘运算小心溢出：在快速幂中间计算时，即使使用 long long，也可能溢出，但题目限定 m ≤ 10⁹，long long 可以安全处理
该算法的时间复杂度约为 O(log n × log m)，空间复杂度为 O(log m)（递归栈深度），能够有效处理 n 和 m 高达 10⁹ 的大规模输入。
