注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Poj2417】【Baby-step-giant-step】【Discrete Logging】  

2014-05-03 22:32:34|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:求BL == N (mod P)的L的最小值或者判断是否无解

   0.0这道题有一个算法叫baby-step-giant-step,也就是说就是这个的裸题的感觉...

   咱们首先设 L=(i*m)+j(0<=j<m),则B^L=B^j*B^(i*m)【m是自己定的】
   然后咱们先求出 B^0~B^(m-1)的解答,存在一个HASH表里面。
   然后咱们就开始枚举i的大小,然后就可以求出B^(i*m)的大小,然后咱们就可以利用exgcd求出B^j的大小,然后咱们在Hash表里面查找即可,如果能找到的话答案就是L=i*m+j,这样的复杂度就是O(sqrt(n)*logn)。
   这里由于模的大小过大...咱们再考虑对得出来的答案hash一个小一点的模,存在HASH表里面。
   这里考虑到m取多少效率最高...显然应该是sqrt(P)最好。

   ps:枚举(i*m)要从0~m枚举,另外= =Poj貌似不支持eof,而只支持seekeof...momo...
   ps2:这里咱没用hash而是二分查找,经试验貌似hash会有很大的冲突233
==================

program poj2417;
const modd=1000007;
var n,b,p,m,ans:int64;
    hash,st:array[0..modd]of int64;

procedure exgcd(a,b:int64;var x,y:int64);
var s,t:int64;
begin
  if b=0 then
   begin
     x:=1;y:=0;
     exit;
   end;
  exgcd(b,a mod b,s,t);
  x:=t;
  y:=s-(a div b)*t;
end;

function invmod(a,n:int64):int64;
var x,y:int64;
begin
  exgcd(a,n,x,y);
  x:=(x mod n+n)mod n;
  exit(x);
end;

procedure qsort(l,r:longint);
var i,j,x,y:int64;
begin
  i:=l;j:=r;
  x:=hash[(l+r)shr 1];
  repeat
    while hash[i]<x do inc(i);
    while hash[j]>x do dec(j);
    if i<=j then
     begin
       y:=hash[i];hash[i]:=hash[j];hash[j]:=y;
       y:=st[i];st[i]:=st[j];st[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

function find(x:int64):longint;
var l,r,mid:longint;
begin
  l:=0;r:=m-1;
  while l<r do
   begin
     mid:=(l+r)shr 1;
     if hash[mid]=x then exit(st[mid]);
     if hash[mid]<x then l:=mid+1
                    else r:=mid-1;
   end;
  if hash[l]=x then exit(st[l])
               else exit(-1);
end;

procedure init;
var i,pos:longint;
    inv,h,w,x,y:int64;
begin
  read(p,b,n);
  inv:=invmod(n,p);
  m:=trunc(sqrt(p));
  h:=1;
  for i:=0 to m do
   begin
     {if hash[h mod modd]<>-1 then write('= =');}
     hash[i]:=h;
     st[i]:=i;
     h:=h*b;
     if h>=p then h:=h mod p;
   end;
  w:=inv;
  qsort(0,m-1);
  for i:=0 to m-1 do
   begin
     exgcd(w,p,x,y);
     x:=(x mod p+p)mod p;
     pos:=find(x);
     if pos<>-1 then
      begin
        ans:=i*m+pos;
        writeln(ans);
        exit;
      end;
     w:=w*h;
     if w>=p then w:=w mod p;
   end;
  writeln('no solution');
end;

begin
  while not seekeof do
    init;
end.



  评论这张
 
阅读(30)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017