算出幂塔函数\(a^a\)共b个a乘幂的结果模m的值。

求a^(a^(a^(a^(a^...)))),a的a次方的a次方的a次方..%m

我只能想到欧拉降幂递归求解,但是要优化,不然会超时(下面那个优化我也没看懂mod的函数为什么要用在快速幂和递归return里面

在这个大佬的博客看到的

#include 
    
     typedef long long LL;LL phi[1000010];LL maxn = 1000005;void phi_table() {    phi[0] = 0, phi[1] = 1;    for(LL i = 2; i < maxn; ++i) phi[i] = i;    for(LL i = 2; i < maxn; ++i) {        if(phi[i] == i) {            for(LL j = i; j < maxn; j += i)                phi[j] = phi[j] / i * (i - 1);        }    }}LL mod(LL a, LL b) {    return a < b ? a : a % b + b;}LL pow_mod(LL a, LL b, LL p) {    LL ret = 1;    while(b) {        if(b & 1) ret = mod(ret * a, p);        a = mod(a * a, p);        b >>= 1;    }    return ret;}LL euler(LL a, LL b, LL c) {    if(b == 1 || c == 1) return mod(a, c);    return pow_mod(a, euler(a, b - 1, phi[c]), c);}int main() {    phi_table();    int t;    LL a, b, m;    scanf("%d", &t);    while(t--) {        scanf("%lld %lld %lld", &a, &b, &m);        if(b == 0 || a == 1) printf("%lld\n", 1ll % m);        else {            LL ans = euler(a, b, m);            printf("%d\n", ans % m);        }    }    return 0;}