BZOJ3844 上帝与集合的正确用法

Description

给定\(p\),求\(2^{2^{2^{2^{2^{\cdots}}}}}mod\; p\)\(p\leqslant 10^7\)

Solution

\(f(p)=2^{2^{2^{2^{2^{\cdots}}}}}mod\; p\)。由于\(b>\phi(p)\)\(a^b\equiv a^{(b\,mod\,\phi(p))+\phi(p)}(mod\;p)\)。所以\(f(p)=2^{f(\phi(p))+\phi(p)}mod\; p\)

由于易证\(\phi(\phi(p))\leqslant\frac p2\),所以时间为\(O(\log p)\)

Code

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
#include <cstdio>
typedef long long LL;
const int N = 10000050;
int phi[N], pr[N / 10], cnt;
int pow_mod(int a, int b, int p) {
int ans = 1;
for (; b; b >>= 1, a = (LL)a * a % p)
if (b & 1) ans = (LL)ans * a % p;
return ans;
}
int calc(int p) {
// 2 ^ (2 ^ (...)) % p
if (p == 1) return 0;
return pow_mod(2, calc(phi[p]) + phi[p], p);
}
int main() {
for (int i = 1; i < N; ++i) phi[i] = i;
for (int i = 2; i < N; ++i) {
if (phi[i] == i)
--phi[pr[cnt++] = i];
for (int j = 0; j < cnt && (LL)pr[j] * i < N; ++j) {
if (i % pr[j])
phi[i * pr[j]] = phi[i] * phi[pr[j]];
else {
phi[i * pr[j]] = phi[i] * pr[j];
break;
}
}
}
int T, p;
scanf("%d", &T);
while (T--) {
scanf("%d", &p);
printf("%d\n", calc(p));
}
}