bzoj 3122 : [Sdoi2013]随机数生成器 BSGS

BSGS算法

转自：http://blog.csdn.net/clove_unique

问题

给定a,b,p，求最小的非负整数x，满足$a^x≡b(mod p)$

题解

这就是经典的BSGS算法，方法如下：
令$x=im−j$，$m=⌈sqrt{p}⌉$，则$a^{im−j}≡b(mod p)$
移项，得$(a^m)^i≡ba^j(mod p) $
首先，从$0−m$枚举$j$，将得到的$ba^j$的值存入hash表；
然后，从$1−m$枚举$i$，计算$(a^m)^i$，查表，如果有值与之相等，则当时得到的$im−j$是最小值。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<map>
  6 #include<cmath>
  7 #define int long long
  8 using namespace std;
  9 int p;
 10 int pw(int x,int y)
 11 {
 12     int lst=1;
 13     while(y)
 14     {
 15         if(y&1)lst=lst*x%p;
 16         y>>=1;
 17         x=x*x%p;
 18     }
 19     return lst;
 20 }
 21 int xx,yy;
 22 void exgcd(int a,int b)
 23 {
 24     if(b==0)
 25     {
 26         xx=1;yy=0;
 27         return ;
 28     }
 29     exgcd(b,a%b);
 30     int tmp=xx;
 31     xx=yy;
 32     yy=tmp-(a/b)*yy;
 33     return ;
 34 }
 35  
 36 map<int,int>mp;
 37 int work(int a,int b)
 38 {
 39      int m=ceil(sqrt(p));
 40      mp.clear();
 41      int now=1;
 42      mp[now*b%p]=0;
 43      for(int i=1;i<=m;i++)
 44      {
 45         now=now*a%p;
 46         mp[now*b%p]=i;
 47      }
 48      int tmp=1;
 49      for(int i=1;i<=m;i++)
 50      {
 51         tmp=tmp*now%p;
 52         if(mp[tmp])
 53         {
 54             return  i*m-mp[tmp];
 55         }
 56      }
 57      return -1;
 58 }
 59 int a,b,x1,t;
 60 signed main()
 61 {
 62     int cas;
 63     scanf("%lld",&cas);
 64     while(cas--)
 65     {
 66         scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&x1,&t);
 67         if(x1==t)
 68         {
 69             puts("1");
 70             continue;
 71         }
 72         if(a==0)
 73         {
 74             if(x1==t)puts("1");
 75             else if(b==t)puts("2");
 76             else puts("-1");
 77             continue;
 78         }
 79         if(a==1)
 80         {
 81             if(!b)
 82             {
 83                 if(x1==t)puts("1");
 84                 else puts("-1");
 85                 continue;
 86             }
 87             exgcd(b,p);
 88             int tmp=(t-x1+p)%p;
 89             xx=((xx*tmp%p)+p)%p;
 90             xx++;
 91             printf("%lld
",xx);
 92         }
 93         else
 94         {
 95             int c=pw(a-1,p-2);
 96             int t1=(x1+b*c)%p,t2=p,t3=(b*c+t)%p;
 97             exgcd(t1,t2);
 98             xx=(xx%p+p)%p;
 99             xx=(xx*t3)%p;
100             int ans=work(a,xx);
101             if(ans!=-1)printf("%lld
",ans+1);
102             else printf("%lld
",ans);
103         }
104     }
105     return 0;
106 }