题解：P1405 苦恼的小明

· · 题解

首先，根据欧拉定理可知：

a^b\equiv a^{b\bmod\phi(p)+\phi(p)}\bmod p

这个定理的好处就在于可以大大降低指数的大小。以下内容用到了这个狮子。

现在来观察题目：若要求 a_1^{a_2^{a_3}}\bmod10007 ，可以先缩小指数，求出 a_2^{a_3}\bmod\phi(10007)\ +\phi(10007)。但还是不够，再一次缩小指数，求出 a_3\bmod\phi(\phi(10007))\ +\phi(\phi(10007))。以此类推，不断缩小指数，最后再使用快速幂取模得出答案。总的来说，整个过程就是先不断向上递归用欧拉定理缩小指数 ，再向下回溯用快速幂求解。

当 a 的数量超过 13 的时候，\phi 值就变成了 1，再往上走就没有啥意义了，直接退出。当然，也可以预先求解出所有的 \phi 值，不多，就 13 个。

update(2024.6.16)：感谢@August_Light 大佬提供的 Hack 数据，发现了代码中存在的漏洞。修复此问题可以直接添加一个特判 a 为 1 时直接返回 1。 

#include<bits/stdc++.h>
using namespace std;
int n, mod[13] = {10007, 10006, 5002, 2400, 640, 256, 128, 64, 32, 16, 8, 4, 2};
inline int getans(int times, int m){
    if(!times || m >= 13) return 1;
    int a, ans = 1, k;
    cin>>a;
    k = getans(times-1, m+1);
    if(a == 1) return 1; // 注意这里 
    while(k){
        if(k & 1) ans = (long long)ans * a % mod[m];
        a = (long long)a * a % mod[m];
        k >>= 1;
    }
    return m?ans + mod[m]:ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>n;
    return cout<<getans(n, 0), 0;
}