题解：P1405 苦恼的小明

· · 题解

根据欧拉定理，我们有：

a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod{m}

那么我们推一波式子：

a_1^{a_2^{\ldots^{a_n}}} \equiv a_1^{(a_2^{\ldots^{a_n}}) \bmod \varphi(m) + \varphi(m)} \equiv a_1^{(a_2^{(a_3^{\ldots^{a_n}}) \bmod \varphi(\varphi(m))+ \varphi(\varphi(m))}) \bmod \varphi(m) + \varphi(m)} \equiv \ldots \pmod{m}

那么我们可以定义函数 f(x,m) 为：

\begin{array}{rcl} 1, & & & x>n\\ 1, & & & m=1\\ a_x^{f(x+1,\varphi(m)) \bmod \varphi(m)+ \varphi(m)} \bmod m,& &&\text{otherwise} \end{array} \right.

递归实现即可。

有人问递归会不会爆栈，我们看一下 m,\varphi(m),\varphi(\varphi(m)),\ldots 的值：

10007,10006,5002,2400,640,256,128,64,32,16,8,4,2,1,\ldots

我们发现，当到第 14 层时，m 就为 1 了，这说明这个函数调用层数为 \min(n,14)，不会爆栈。

那么这道题就解决了，代码如下：

ll phi(ll x) {
    ll res = x;
    int t = x;
    for (ll i = 2; i * i <= t; i++) {
        if (x % i == 0) {
            res = res * (i - 1) / i;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res * (x - 1) / x;
    return res;
}
int n;
ll a[1234568];
ll f(ll now, ll p) {
    if (now > n) return 1;
    if (p == 1) return 1;
    return quick_pow(a[now], f(now + 1, phi(p)) % phi(p) + phi(p), p);
}
int main() {
    read(n);
    rep(i, 1, n, 1) {
        read(a[i]);
    }
    write(f(1, 10007));
}