上帝与集合的正确用法

题目大意

求:

2{222222mod  p无数个2 \left\{ 2 ^{2^{2^{2^{2^{2 \cdots}}}}} \right. \bmod \; p

多组询问。

1T1,0001 \leqslant T \leqslant 1,000

1p10,000,0001 \leqslant p \leqslant 10,000,000

题目链接

上帝与集合的正确用法 - Luogu 4139

题解

pp 分解为 p=2kqp = 2^k qqq 为奇数,与 22 互质,那么有:

\begin{align} 2^{2^{2^{2 \cdots}}} \bmod \; p &= 2^k (2^{2^{2^{2 \cdots}} - k} \bmod \; q) \\ &= 2^k (2^{(2^{2^{2 \cdots}} - k) \bmod \; \varphi (q)} \bmod \; q) \end{align}

指数部分与原式相同,模数变小(至少除以 22),故可以递归计算。模数最终会变为 11,而任何数模 11 均为 00

代码

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>
int phi(int x) {
int res = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int pow(long long a, int n, int mod) {
long long res = 1;
for (; n; n >>= 1, a = a * a % mod) if (n & 1) res = res * a % mod;
return (int) res % mod;
}
int solve(int p) {
if (p == 1) return 0;
int k = 0;
while ((p & 1) == 0) p >>= 1, k++;
int phiQ = phi(p);
int temp = (solve(phiQ) - k % phiQ + phiQ) % phiQ;
int res = pow(2, temp, p);
return res << k;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int p;
scanf("%d", &p);
printf("%d\n", solve(p));
}
return 0;
}