Article From:

The input data of this question need to be a and B both%p.

At the complexity of about sqrt (P), the X in (a^x)% P = B% P is obtained.

Extended bsgs increases the handling of P not prime.

The extension bsgs does not handle the part of the num below when bsgs is processed after a, B, and P is processed, and this part deals with a, B, P and so on (b=1 output Num), so it is not considered.

So in fact, extending bsgs and common bsgs only have more than one cycle of processing.

acAfter one time, I deleted parts of the excess (non – pre – processing cycle) to determine a==b and b==1, and it was true that the beginning of these unnecessary parts was gilding.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<map>
 7 using namespace std;
 8 #define LL long long
 9 LL p,a,b;
10 map<LL,LL>q;
11 LL mgcd(LL x,LL y){return y==0?x:mgcd(y,x%y);}
12 int main(){
13     while(~scanf("%lld%lld%lld",&a,&p,&b)){
14         if(a==0&&p==0&&b==0)break;b=b%p;a=a%p;
15         LL x=1,y=1,t=0,d=mgcd(a,p),ff=0;
16         while(d!=1){
17             if(b==1){printf("%lld\n",t);ff=1;break;}
18             if(b%d!=0){printf("No Solution\n");ff=1;break;}
19             ++t;a/=d;b/=d;p/=d;
20             y=(y*a)%p;a=a*d;
21             d=mgcd(a,p);
22         }if(ff)continue;
23         a%=p;b%=p;
24         LL w=(LL)sqrt((double)p);if(w*w!=p)++w;
25         q[b]=-1; for(int i=1;i<=w;++i){x=(x*a)%p;LL z=(b*x)%p;q[z]=i;}
26         bool f=0;LL m=10000000000000000LL;
27         for(int i=1;i<=w;++i){
28             y=(y*x)%p;
29             if(q[y]!=0){
30                 LL z=q[y];if(z==-1) z=0;
31                 z=(LL)i*w-z;f=1;
32                 m=min(z+t,m);
33             }
34         }
35         q[b]=0;x=1;
36         for(int i=1;i<=w;++i){x=(x*a)%p;LL z=(b*x)%p;q[z]=0;}
37         if(!f)printf("No Solution\n");
38         else printf("%lld\n",m);
39     }
40     return 0;
41 }

View Code


Link of this Article: POJ 3243 Clever Y extended BSGS

Leave a Reply

Your email address will not be published. Required fields are marked *