题意分析

本题要求计算一个通过多重幂运算（tower exponentiation）递归定义的函数 $f(i)$的最后 n 位数字。函数定义为：

$f(0) = 1$

$f(x) = b ^ f(x-1)$ （当 x > 0 时）

由于 f(i) 的值会迅速增长成一个极大的数，直接计算完整结果既不现实也效率低下，因此需要采用数论中的技巧来计算模运算结果。本题目标是计算 $f(i) mod 10^n$。

解题关键点

1、指数递归增长 由于 $f(i)$ 以指数的形式递归增长，即 $f(i) = b ^ f(i-1)$，直接计算 $f(i)$ 会导致数值暴涨。因此必须在递归过程中利用模运算截取需要的位数。

2、模运算与欧拉定理 本题为了避免直接计算大数，主要涉及利用数论中的欧拉函数及模幂运算对递归的指数运算进行快速模运算。要计算 b 的大指数次幂的模结果，可借助模幂运算。对于模数 $M = 10^n$，使用欧拉定理可以将问题转化为计算指数模 φ(M) 后再进行模幂运算。欧拉定理告诉我们，在满足条件的情况下：

$b^k mod M = b^(k mod φ(M)) mod M$

因此，在递归计算 $f(i)$ 时，可先计算出 $f(i-1)$ 对 $φ(10^n)$ 的模，然后用该值作为指数进行模幂运算。

3、降低指数规模 对于 $f(i) = b ^ f(i-1) mod (10^n)$ 来说，计算 $f(i-1)$ 的值通常远大于 $φ(10^n)$，因此在模运算时需要先递归地将指数对 $φ(10^n)$ 取模，降低指数的规模，再进行 $b$ 的模幂运算。

解题思路

1、数据处理 计算所需的 $φ$ 值。对于模数 $M = 10^n$，可以预先计算出其欧拉函数值 $φ(M)$。代码中通过函数 $phi$ 计算了任意整数 n 的 $φ$ 值。

2、模幂运算 利用模幂运算函数 $mod_exp(b, t, M)$ 快速计算 $b^t mod M$，避免直接计算大数幂。

3、递归计算 $f(i)$ 使用递归函数 $calc(B, T, M)$ 实现递归关系：

递归终止：当 $T == 0$ 返回 1。

递归下降：先计算 $t = calc(B, T-1, φ(M))$，即 $f(T-1)$ 对 $φ(M)$ 的模值。

应用模幂运算：计算 $mod_exp(B, t, M)$ 得到 $f(T) mod M$。

本题代码

#include <cstdio>
#include <cstring>
#define N 100 + 5
typedef long long ll;
ll newmod(ll a, ll b) {
	return a <= b ? a : b + a % b;
}
int phi(int n) {
	int phi = n, i, j;
	for (i = 2, j = 4; j <= n; i++, j += i + i - 1)
		if (!(n % i)) {
			phi = phi / i * (i - 1);
			while (!(n % i))
				n /= i;
		}
	if (n > 1) phi = phi / n * (n - 1);
	return phi;
}

ll mod_exp(ll a, ll b, ll n) {
	ll hash = 1, factor = a, x = b;
	while (x) {
		if (x & 1) hash = newmod(hash * factor, n);
		factor = newmod(factor * factor, n);
		x >>= 1;
	}
	return hash;
}
// Calc B^B^B....^B mod M (The number of B is T)
int calc(ll B, ll T, ll M) {
	if (T == 0) return 1LL;
	int ph = phi(M);
	int t = calc(B, T - 1, ph);//Euler Law:a^b = (a ^ (b mod phi(m)) (mod m)
	return mod_exp(B, t, M);
}
int ans[N][N];
void solve(int b, int i, int n) {
	int x;
	if (ans[b][i] == -1) x = ans[b][i] = calc(b, i, 10000000) % 10000000;
	x = ans[b][i];
	char line[10];
	sprintf(line, "%.7d", x);
	puts(line + (7 - n));

}

int main() {
	int b, n, i;
	memset(ans, -1, sizeof(ans));
	while (scanf("%d", &b) && b) {
		scanf("%d%d", &i, &n);
		solve(b, i, n);
	}

	return 0;
}