BZOJ

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.