BZOJ 2242

传送门

尼玛每次BSGS忘了清空哈希一直冲突搞了我一上午 然而还是会冲突,所以要拉链…

第一问…直接快速幂

第二问…费马小定理,所以快速幂 因为我又忘了扩展欧几里得怎么写啊QAQ

第三问…BSGS,搞法如下

设$m=\lceil sqrt(p)\rceil,x=i\times m+j,j\in[0,m)$

$Y^x=Y^{i\times m+j}$

$Y^{i\times m+j}\equiv Z(mod\ p)$

$Y^j\equiv Z\times Y^{-i\times m}(mod\ p)$

处理出来$j\in[1,m)$的所有$Y^j$,存到哈希表里,然后枚举后面那一坨中的$i$,若哈希表中出现过就输出答案跳出

那么问题来了,求$Y^m$逆元技术哪家强?

它的逆元即为$(Y^m)^{p-2}$

$(Y^m)^{p-2}=Y^{m\times(p-2)}$

因为$p$为质数,由欧拉定理得$Y^{m\times(p-2)}=Y^{(m\times(p-2))mod\ \varphi(p)}=Y^{(m\times(p-2))mod\ (p-1)}=Y^{(m\times(p-1)-m)mod\ (p-1)}=Y^{p-m-1}$

这样就能求后面那一项了

我的哈希不拉链会冲突 = = 没有map的P党你们伤不起啊QAQ


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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
program bzoj_2242;
const mo=100007;
var t,k,i:longint;
y,z,p:int64;
h:array[0..mo,1..2]of record p:longint; k:int64; end;
cnt:array[0..mo]of longint;
function mul(a,b:int64):int64;
begin
mul:=0;
while b>0 do
begin
if b and 1=1 then mul:=(mul+a)mod p;
a:=a<<1 mod p;
b:=b>>1;
end;
end;
function qpower(x,k:int64):int64;
var ans:int64;
begin
ans:=1;
while k>0 do
begin
if k and 1=1 then ans:=mul(ans,x);
x:=mul(x,x);
k:=k>>1;
end;
exit(ans);
end;
function hash(x:int64):longint;
var h:longint;
begin
h:=0;
while x>0 do
begin
h:=(h*31+x mod 10)mod mo;
x:=x div 10;
end;
exit(h);
end;
procedure BSGS;
var m,t,yy,zz:int64;
i,j,s:longint;
begin
fillchar(cnt,sizeof(cnt),0);
m:=trunc(sqrt(p)+1-(1e-3));
t:=1;
for i:=1 to m-1 do
begin
t:=mul(t,y);
s:=hash(t);
inc(cnt[s]);
h[s,cnt[s]].p:=i;
h[s,cnt[s]].k:=t;
end;
yy:=qpower(y,p-m-1);
zz:=z;
for i:=0 to m-1 do
begin
s:=hash(zz);
for j:=1 to cnt[s] do if h[s,j].k=zz then
begin
writeln(m*i+h[s,j].p);
exit;
end;
zz:=mul(zz,yy);
end;
writeln('Orz, I cannot find x!');
end;
begin
readln(t,k);
for i:=1 to t do
begin
readln(y,z,p);
if k=1 then
begin
writeln(qpower(y,z));
continue;
end;
y:=y mod p;
z:=z mod p;
if (y=0)and(z<>0) then
begin
writeln('Orz, I cannot find x!');
continue;
end;
if k=2 then writeln(mul(qpower(y,p-2),z));
if k=3 then if y=0 then writeln('1') else BSGS;
end;
end.