正文
Baby Step Gaint Step
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
给定同余式
，求它在
内的所有解，其中
总是素数。
分析： 解本同余式的步骤如下
（1）求模
的一个原根
（2）利用
Baby Step Giant Step
求出一个
，使得
，因为
为素数，所以有唯一解。
（3）设
，这样就有
，其中
，那么得到
。
（4）求出所有的
，可以知道一共有
个解，我们求出所有的
，然后排个序即可。
O(sqrt(n))的时间复杂度
BSGS如下（前向星版本）
const maxn=; type node=record
data,next,id:longint;
end; type LL=int64; var edge:array [..maxn] of node;
head:array [..maxn] of longint;
cnt:longint;
a,b,c:ll; procedure insert(data,id:longint);
var i,k:longint;
begin
k:=data mod maxn;
i:=head[k];
while i<>- do
begin
if edge[i].data=data then exit;
edge[cnt].data:=data;
edge[cnt].id:=id;
edge[cnt].next:=head[k];
head[k]:=cnt;
inc(cnt);
i:=edge[i].next;
end;
end; function find(data:ll):longint;
var i,k:longint;
begin
k:=data mod maxn;
i:=head[k];
while i<>- do
begin
if edge[i].data=data then exit(edge[i].id);
i:=edge[i].next;
end;
exit(-);
end; procedure extend_gcd(a,b:ll;var x,y:ll);
var t:ll;
begin
if b= then
begin
x:=;
y:=;
exit;
end;
extend_gcd(b,a mod b,x,y);
t:=x;
x:=y;
y:=t-(a div b)*y;
end; function gcd(x,y:ll):ll;
begin
if x mod y= then exit(y)
else exit(gcd(y,x mod y));
end; function modd(x,p:ll):ll;
begin
if x>=p then exit(x mod p);
if x< then exit((x mod p+p) mod p);
exit(x);
end; function quick_mod(a,n,p:ll):ll;
var ans,t:ll;
begin
ans:=; t:=modd(a,p);
while n<> do
begin
if (n and )= then ans:=modd(ans*t,c);
n:=n>>;
t:=modd(t*t,c);
end;
exit(ans);
end; function bsgs(a,b,c:ll):ll;
var x,y,k,t,d,len,m:ll; i:longint;
begin
fillchar(head,sizeof(head),$ff);
cnt:=;
b:=modd(b,c);
for i:= to do
begin
if b=t then exit(i);
t:=modd(t*a,c);
end;
d:=; len:=;
while true do
begin
t:=gcd(a,c);
if t= then break;
if (b mod t)<> then exit(-);
c:=c div t;
b:=b div t;
d:=modd(d*a div t,c);
inc(len);
end;
m:=trunc(sqrt(c));
t:=;
for i:= to m do
begin
insert(t,i);
t:=modd(t*a,c);
end;
k:=quick_mod(a,m,c);
for i:= to m do
begin
extend_gcd(d,c,x,y);
t:=modd(b*x,c);
if (y=find(t)) and (y<>-) then exit(i*m+y+len);
d:=modd(d*k,c);
end;
exit(-);
end; begin
readln(a,b,c);
writeln(bsgs(a,b,c));
end.
