计蒜客 41299 - super log

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2019 南京网络赛 B 题

思路

题目要求 \[ a^{a^{a^{\cdots}}}  \pmod{m}\] 其中共有\(b\)个\(a\)。 考虑欧拉函数降幂。我们常用的欧拉函数降幂是这样的： \[ a^b \equiv \left\{ \begin{aligned} & a^{b \bmod \varphi(m)} & {\rm gcd}(a, m)=1 \\ & a^b &{\rm gcd}(a, m)\neq 1, b < \varphi(m) \\ & a^{b \bmod\varphi(m) +\varphi(m)} &{\rm gcd}(a, m)\neq 1, b \geq \varphi(m)  \end{aligned} \right . \pmod{m} \] 其中第一个式子是被包含在后两个式子当中的。那么对于我们要求的式子，记\(f(a,b,m)\)为\(b\)个\(a\)在这种形式下对\(m\)取模的值，记\(t(a,b)\)为\(b\)个\(a\)在这种形式下的值。我们可以得这样的递推关系，当\(t(a,b) < \varphi(m)\)时，我们可以直接递归求\(t(a,b)\)，否则\(f(a,b,m) = a^{f(a,b-1,\varphi(m)) + \varphi(m)} \pmod{m}\)。在判断\(t(a,b)\)和\(\varphi(m)\)的时候，由于\(t(a,b)\)增长的速度很快，对于\(a \geq 3\)，只要\(b \geq 2\)，一定满足\(t(a,b) \geq m\)，其他情况特判即可。由于不断的对\(m\)取\(\varphi(m)\)，所以第三个参数会很快收敛到\(1\)，所以跑得很快。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000000 + 5;
LL vis[MAX_N];
LL p[MAX_N], phi[MAX_N], tot;
void linearSieve() {
    vis[0] = vis[1] = 1;
    phi[1] = 1;
    for (LL i = 2; i < MAX_N; ++i) {
        if (!vis[i]) {
            p[++tot] = i;
            phi[i] = i - 1;
        }
        for (LL j = 1; j <= tot && i * p[j] < MAX_N; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            } else {
                phi[i * p[j]] = phi[i] * phi[p[j]];
            }
        }
    }
}
inline LL getPow(LL x, LL y, LL P) {
    LL ret = 1 % P;
    while (y) {
        if (y & 1) ret = ret * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ret;
}
LL T;
LL a, b, m;
// u ^ v < P
bool check(LL u, LL v, LL P) {
    if (v == 0) return 1 < P;
    if (u >= P) return false;
    if (u == 1) return u < P;
    if (u == 2) {
        if (v >= 5) return false;
        else {
            if (v == 1) return 2 < P;
            if (v == 2) return 4 < P;
            if (v == 3) return 16 < P;
            if (v == 4) return 65536 < P;
        }
    }
    if (u >= 3) {
        if (v >= 2) return false;
        else return u < P;
    }
}
LL f(LL u, LL v) {
    if (v == 0) return 1;
    else return getPow(u, f(u, v - 1), LL(1E18));
}
LL solve(LL u, LL v, LL P) {
    // printf("Call solve(%lld, %lld, %lld)\n", u, v, P);
    if (P == 1) return 0;
    if (v == 1) return u % P;
    LL t = phi[P];
    if (check(u, v - 1, t)) return f(u, v) % P;
    else return getPow(u, solve(u, v - 1, t) + t, P);
}
int main() {
    linearSieve();
    scanf("%lld", &T);
    for (LL cs = 1; cs <= T; ++cs) {
        scanf("%lld%lld%lld", &a, &b, &m);
        printf("%lld\n", solve(a, b, m));
    }
    return 0;
}