【poj3243-Clever Y】高次同余方程-拓展BabyStepGiantStep

题意：给定X,Z,K，求一个最小的Y满足X^Y mod Z = K。

关于拓展BSGS的详细解释我写了一篇博文：http://www.cnblogs.com/KonjakJuruo/p/5178600.html

题解：BSGS的拓展版本(因为X和Z不一定互质)。这道题挺坑的，如果K>=Z不是输出无解而是让K%=Z。

算是BSGS的模板题，我打了两种版本，就是二分查找和hash。对比两次提交来看，二分省空间，耗时间；Hash省时间，耗空间。

　　另外，find部分可以不用二分，而用hash解决。感觉大部分情况下还是hash比较快，但是比较耗空间。

　　把你需要存的数，即x的0~m次方算出来，假设是t，我们设m=1<<16-1，然后用t异或^m得nt（就是取t二进制后的15位进行hash），然后存到hash表里面去。如果t的位置目前没有存数，那么我们就直接存到hash[t]上去，如果t位置已经存了数（因为后15位为t的可能有多种情况），我们就在len除增加一个位置，把nt存到那里面去，然后hash[t].next=len，把位置记录下来，这应该就相当于一条链了。查找的时候循着这条链找下去即可，链的尽头的next用-1标记。

——引用自http://www.cnblogs.com/Konjakmoyu/p/5180458.html

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 typedef long long LL;
 10 const int N=40000;
 11 bool bk;
 12 LL X,Z,K,a,b,c,m,k,sum,am,bl;
 13 struct node{
 14     LL d,id;
 15 }bit[N],p[N];
 16 
 17 bool cmp(node x,node y){
 18     if(x.d!=y.d) return x.d<y.d;
 19     return x.id<y.id;
 20 }
 21 
 22 LL gcd(LL u,LL v)
 23 {
 24     if(v==0) return u;
 25     return gcd(v,u%v);
 26 }
 27 
 28 LL find(LL x)
 29 {
 30     int l=0,r=bl;
 31     while(l<=r)
 32     {
 33         int mid=(l+r)>>1;
 34         if(bit[mid].d==x) return bit[mid].id;
 35         if(bit[mid].d>x) r=mid-1;
 36         if(bit[mid].d<x) l=mid+1;
 37     }
 38     return -1;
 39 }
 40 
 41 void exgcd(LL u,LL v,LL &x,LL &y)
 42 {
 43     if(v==0) {x=1,y=0;return ;}
 44     LL tx,ty;
 45     exgcd(v,u%v,tx,ty);
 46     x=ty;y=tx-(u/v)*ty;
 47     return;
 48 }
 49 
 50 LL BSGS()
 51 {
 52     LL t,g,x,y,pm;
 53     a=X;b=K;c=Z;k=1;sum=0;bk=1;bl=0;t=1%c;
 54     for(int i=0;i<=100;i++){//避免a的负数次方
 55         if(t==b) return i;
 56         t=t*a%c;
 57     }
 58     while((g=gcd(X,c))!=1)
 59     {
 60         k=(k*X/g)%c;//k记得要mod，否则溢出
 61         c/=g;
 62         if(b%g) return -1;
 63         b/=g;
 64         sum++;
 65     }
 66     m=(LL)(ceil((double)sqrt((double)c)));//要约分之后再求m
 67     p[0].d=k%c;
 68     p[0].id=0;
 69     pm=1;//pm是不用*k的
 70     for(int i=1;i<=m;i++) 
 71         p[i].d=p[i-1].d*a%c,pm=pm*a%c,p[i].id=i;
 72     sort(p,p+1+m,cmp);
 73     bit[0]=p[0];bl=0;
 74     for(int i=1;i<=m;i++)
 75     {
 76         if(p[i].d!=p[i-1].d) bit[++bl]=p[i];
 77     }
 78     exgcd(pm,c,x,y);
 79     am=(x%c+c);//避免am=0
 80     
 81     t=b;
 82     x=find(b);
 83     if(x!=-1) return x;
 84     for(int i=1;i<=bl;i++)
 85     {
 86         t*=am;t%=c;
 87         x=find(t);
 88         if(x!=-1)
 89             return i*m+x;
 90     }
 91     return -1;
 92 }
 93 
 94 int main()
 95 {
 96     // freopen("a.in","r",stdin);
 97     // freopen("a.out","w",stdout);
 98     while(1)
 99     {
100         scanf("%I64d%I64d%I64d",&X,&Z,&K);
101         if(!X && !Z && !K) return 0;
102         K%=Z;
103         LL ans=BSGS();
104         if(ans!=-1) printf("%I64d
",ans+sum);
105         else printf("No Solution
");
106     }
107     return 0;
108 }

BSGS-二分

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 typedef long long LL;
 10 const LL N=40000,Max=(1<<16)-1;
 11 bool bk;
 12 LL X,Z,K,len;
 13 bool vis[70000];
 14 struct node{
 15     LL d,id,next;
 16 }hash[2*Max];
 17 
 18 int exgcd(LL a,LL b,LL &x,LL &y)
 19 {
 20     if(b==0) {x=1,y=0;return a;}
 21     LL tx,ty;
 22     LL d=exgcd(b,a%b,tx,ty);
 23     x=ty;y=tx-(a/b)*ty;
 24     return d;
 25 }
 26 
 27 void ins(LL d,LL id)
 28 {
 29     LL t=d&Max;
 30     if(!vis[t]) {
 31         vis[t]=1;
 32         hash[t].d=d,hash[t].id=id,hash[t].next=-1;
 33         return ;
 34     }
 35     for(;hash[t].next!=-1;t=hash[t].next))//注意是hash[t].next!=-1
 36     {
 37         if(hash[t].d==d) return;
 38     }
 39     hash[t].next=++len;
 40     hash[len].d=d;hash[len].id=id;hash[len].next=-1;
 41 }
 42 
 43 LL find(LL d)
 44 {
 45     LL t=d&Max;
 46     if(!vis[t]) return -1;
 47     for(;t!=-1;t=hash[t].next)
 48     {
 49         if(hash[t].d==d) return hash[t].id;
 50     }
 51     return -1;
 52 }
 53 
 54 LL BSGS()
 55 {
 56     LL t,g,x,y,pm,a,b,c,m,k,sum,am;
 57     a=X;b=K;c=Z;k=1;sum=0;t=1%c;
 58     for(int i=0;i<=100;i++){
 59         if(t==b) return i;
 60         t=t*a%c;
 61     }
 62     while((g=exgcd(X,c,x,y))!=1)
 63     {
 64         k=(k*X/g)%c;
 65         c/=g;
 66         if(b%g) return -1;
 67         b/=g;
 68         sum++;
 69     }
 70     m=(LL)(ceil((double)sqrt((double)c)));
 71     ins(k,0);
 72     t=k;pm=1;
 73     for(int i=1;i<=m;i++)
 74     {
 75         t=t*a%c,pm=pm*a%c;
 76         ins(t,i);
 77     }        
 78     exgcd(pm,c,x,y);
 79     am=x%c+c;
 80     t=b;
 81     for(int i=0;i<=m;i++)
 82     {
 83         x=find(t);
 84         if(x!=-1) return i*m+x+sum;
 85         t=t*am%c;
 86     }
 87     return -1;
 88 }
 89 
 90 int main()
 91 {
 92     // freopen("a.in","r",stdin);
 93     // freopen("b.out","w",stdout);
 94     while(1)
 95     {
 96         scanf("%I64d%I64d%I64d",&X,&Z,&K);
 97         if(!X && !Z && !K) return 0;
 98         K%=Z;len=Max;
 99         memset(vis,0,sizeof(vis));
100         LL ans=BSGS();
101         if(ans!=-1) printf("%I64d
",ans);
102         else printf("No Solution
");
103     }
104     return 0;
105 }

BSGS-Hash