exBSGS模板

 1 program j01;
 2 const mo=1000007;
 3 var head:array[0..mo]of int64;
 4     hash,next,data:array[0..mo]of int64;
 5     a,b,p,tt:int64;
 6  
 7 function gcd(a,b:int64):int64;
 8 begin
 9   if b=0 then exit(a) else exit(gcd(b,a mod b));
10 end;
11  
12 function pow(a,i,mm:int64):int64;
13 var y:int64;
14 begin
15   if i=0 then exit(1);
16   y:=pow(a,i div 2,mm) mod mm;
17   y:=y*y mod mm;
18   if i mod 2=1 then y:=y*a mod mm;
19   exit(y);
20 end;
21   
22 procedure push(i,w:int64);
23 var x:int64;
24 begin
25   x:=i mod mo;
26   inc(tt);
27   hash[tt]:=i;data[tt]:=w;
28   next[tt]:=head[x];
29   head[x]:=tt;
30 end;
31  
32 function find(i:int64):int64;
33 var j:int64;
34 begin
35   j:=head[i mod mo];
36   while j>0 do
37   begin
38     if hash[j]=i then exit(data[j]);
39     j:=next[j];
40   end;
41   exit(-1);
42 end;
43   
44 procedure solve;
45 var i:longint;
46     n,now,tmp,x,m,d,cnt,t:int64;
47 begin
48   a:=a mod p;b:=b mod p;
49   if b=1 then
50   begin
51     writeln(0);exit;
52   end;
53   cnt:=0;t:=1;
54   while true do
55   begin
56     d:=gcd(a,p);
57     if d=1 then break;
58     if b=t then
59     begin
60       writeln(cnt);exit;
61     end;
62     if not(b mod d=0) then
63     begin
64        writeln(‘No Solution‘);exit;
65     end;
66     p:=p div d;b:=b div d;t:=(t*a div d)mod p;
67     inc(cnt);
68   end;
69   tt:=0;fillchar(head,sizeof(head),0);
70   m:=trunc(sqrt(p))+1;b:=b mod p;
71   now:=b;push(now,0);
72   for i:=1 to m do
73   begin
74     now:=now*a mod p;
75     push(now,i);
76   end;
77   tmp:=pow(a,m,p);
78   now:=t;
79   for i:=1 to m do
80   begin
81     now:=now*tmp mod p;
82     x:=find(now);
83     if x>-1 then
84     begin
85       writeln(i*m-x+cnt);
86       exit;
87     end;
88   end;
89   writeln(‘No Solution‘);
90 end;
91  
92 begin
93   while true do
94   begin
95     readln(a,p,b);
96     if (a=0)and(b=0)and(p=0) then break;
97     solve;
98   end;
99 end.