BZOJ

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)$和原式有点像

似乎奇数的欧拉函数都是偶数

然后先把$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.