BZOJ 3884

传送门

$$2^{2^{2^{2^{2\cdots}}}}\ mod\ p$$

Orz PoPoQQQ

将$p$分解为$2^k$与一个奇数的积: $p=2^k \cdot q$,原式即为

$$2^k(2^{(2^{2^{2^{2\cdots}}}-k)}mod\ q)mod\ p$$

欧拉定理

$$2^k(2^{(2^{2^{2^{2\cdots}}}-k)mod\ \varphi(q)}mod\ q)mod\ p$$

发现上面的一坨$(2^{2^{2^{2\cdots}}}-k)mod\ \varphi(q)$似乎和原式有点像啊

Tips: 经打表可得:似乎奇数的欧拉函数都是偶数的说

然后先把$mod\ \varphi(q)$意义下的$-k$扔到一边一会再算,递归化简这个式子,发现递归的终点是$(2^{2^{2^{2^{2\cdots}}}}-k)\ mod\ 1$

而任何数$mod\ 1$都是$0$,然后…就搞完了…回溯算算就行了

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
program bzoj_3884;
var t,p:longint;
function calc_phi(x:longint):longint;
var cnt,i:longint;
begin
cnt:=x;
for i:=2 to trunc(sqrt(x)) do if x mod i=0 then
begin
cnt:=cnt div i*(i-1);
while x mod i=0 do x:=x div i;
end;
if x=1 then exit(cnt) else exit(cnt div x*(x-1));
end;
function qp(x,k,m:longint):longint;
var p:int64;
begin
qp:=1;
p:=x;
while k<>0 do
begin
if k and 1=1 then qp:=(qp*p)mod m;
p:=(p*p)mod m;
k:=k>>1;
end;
end;
function count(p:longint):longint;
var k,phi,ans:longint;
begin
if p=1 then exit(0);
k:=0;
while p and 1=0 do
begin
p:=p>>1;
inc(k);
end;
phi:=calc_phi(p);
ans:=(count(phi)+phi-k mod phi)mod phi;
exit((qp(2,ans,p)mod p)<<k);
end;
begin
readln(t);
for t:=1 to t do
begin
readln(p);
writeln(count(p));
end;
end.