【算法乱讲】BSGS

Description

Given a prime P, 2 <= P < 2³¹, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that B^L== N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

Sample Input

5 2 1

5 2 2

5 2 3

5 2 4

5 3 1

5 3 2

5 3 3

5 3 4

5 4 1

5 4 2

5 4 3

5 4 4

12345701 2 1111111

1111111121 65537 1111111111

Sample Output

0

1

3

2

0

3

1

2

0

no solution

no solution

1

9584351

462803587

显然，这是一道bsgs的裸题
那么bsgs是什么玩意呢，
我们先玩一玩式子
令 m=ceil(sqrt(p))设a^(m*i+j)=b(mod p)

显然 a^j*a^(m*i)=b(mod p)　
　    a^j=b*a^(-m*i) (mod p)

因此，我们预处理所有可能的a^j丢进哈希表中然后我们枚举i，
看看有没有可能对应的j所以我们的算法时间复杂度为O(n^0.5)

 #include<stdio.h>

 #include<stdlib.h>

 #include<iostream>

 #include<string>

 #include<string.h>

 #include<algorithm>

 #include<math.h>

 #include<queue>

 #include<map>

 #include<vector>

 #include<set>

 #define il inline

 #define re register

 using namespace std;

 typedef long long ll;

 struct hash_set{

     ll v[];

     int next[],g[],w[],tot;

     il void clear(){

         memset(g,false,sizeof(g));tot=;

     }

     il void insert(ll h,int f){

         v[++tot]=h;

         w[tot]=f;

         next[tot]=g[h%];

         g[h%]=tot;

     }

     il int find(ll h){

         for(re int i=g[h%];i;i=next[i])

             if(h==v[i]) return w[i];

         return -;

     }

 } p;

 ll A,B,P,m,t,s;

 il ll ksm(re ll base,re ll pow){

     if(pow<){

         cout<<"-1";exit();

     }

     ll ans=;

     for(;pow;pow>>=){

         if(pow&) ans=ans*base%P;

         base=base*base%P;

     }

     return ans;

 }

 il ll rev(re ll a){

     return ksm(a,P-);

 }

 il void init(){

     p.clear();

     m=ceil(sqrt(P));t=;

     for(int i=;i<m;i++){

         if(p.find(t)<) p.insert(t,i);

         t=t*A%P;

     }

     //cout<<endl;

     for(int i=,l;i<=P/m;i++){

         t=rev(ksm(A,m*i));

     //    cout<<t<<" "<<m*i<<" ";

         s=t*B%P;

     //    cout<<s<<endl;

         l=p.find(s);

         if(l>=){

             printf("%lld\n",m*i+l);

             return;

         }

     }

     printf("no solution\n");

 }

 int main(){

     while(scanf("%lld%lld%lld",&P,&A,&B)!=EOF){

         init();

     }

     return ;

 }

巴特西

【算法乱讲】BSGS

最新文章

热门文章