首页 > 代码库 > Baby Step Gaint Step
Baby Step Gaint Step
给定同余式
分析：解本同余式的步骤如下
（1）求模
（2）利用Baby Step Giant Step求出一个
（3）设
（4）求出所有的
O(sqrt(n))的时间复杂度
BSGS如下（前向星版本）
const maxn=200001;type node=record data,next,id:longint;end;type LL=int64;var edge:array [0..maxn] of node; head:array [0..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<>-1 do begin if edge[i].data=http://www.mamicode.com/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<>-1 do begin if edge[i].data=http://www.mamicode.com/data then exit(edge[i].id); i:=edge[i].next; end; exit(-1);end;procedure extend_gcd(a,b:ll;var x,y:ll);var t:ll;begin if b=0 then begin x:=1; y:=0; 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=0 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<0 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:=1; t:=modd(a,p); while n<>0 do begin if (n and 1)=1 then ans:=modd(ans*t,c); n:=n>>1; 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:=0; b:=modd(b,c); for i:=0 to 100 do begin if b=t then exit(i); t:=modd(t*a,c); end; d:=1; len:=0; while true do begin t:=gcd(a,c); if t=1 then break; if (b mod t)<>0 then exit(-1); c:=c div t; b:=b div t; d:=modd(d*a div t,c); inc(len); end; m:=trunc(sqrt(c)); t:=1; for i:=0 to m do begin insert(t,i); t:=modd(t*a,c); end; k:=quick_mod(a,m,c); for i:=0 to m do begin extend_gcd(d,c,x,y); t:=modd(b*x,c); if (y=find(t)) and (y<>-1) then exit(i*m+y+len); d:=modd(d*k,c); end; exit(-1);end;begin readln(a,b,c); writeln(bsgs(a,b,c));end.
Baby Step Gaint Step
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。