http://poj.org/problem?id=3243
题意：给定X,Z,K，求一个最小的Y满足XY 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标记。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL;
const int N=;
bool bk;
LL X,Z,K,a,b,c,m,k,sum,am,bl;
struct node{
LL d,id;
}bit[N],p[N]; bool cmp(node x,node y){
if(x.d!=y.d) return x.d<y.d;
return x.id<y.id;
} LL gcd(LL u,LL v)
{
if(v==) return u;
return gcd(v,u%v);
} LL find(LL x)
{
int l=,r=bl;
while(l<=r)
{
int mid=(l+r)>>;
if(bit[mid].d==x) return bit[mid].id;
if(bit[mid].d>x) r=mid-;
if(bit[mid].d<x) l=mid+;
}
return -;
} void exgcd(LL u,LL v,LL &x,LL &y)
{
if(v==) {x=,y=;return ;}
LL tx,ty;
exgcd(v,u%v,tx,ty);
x=ty;y=tx-(u/v)*ty;
return;
} LL BSGS()
{
LL t,g,x,y,pm;
a=X;b=K;c=Z;k=;sum=;bk=;bl=;t=%c;
for(int i=;i<=;i++){//避免a的负数次方
if(t==b) return i;
t=t*a%c;
}
while((g=gcd(X,c))!=)
{
k=(k*X/g)%c;//k记得要mod，否则溢出
c/=g;
if(b%g) return -;
b/=g;
sum++;
}
m=(LL)(ceil((double)sqrt((double)c)));//要约分之后再求m
p[].d=k%c;
p[].id=;
pm=;//pm是不用*k的
for(int i=;i<=m;i++)
p[i].d=p[i-].d*a%c,pm=pm*a%c,p[i].id=i;
sort(p,p++m,cmp);
bit[]=p[];bl=;
for(int i=;i<=m;i++)
{
if(p[i].d!=p[i-].d) bit[++bl]=p[i];
}
exgcd(pm,c,x,y);
am=(x%c+c);//避免am=0 t=b;
x=find(b);
if(x!=-) return x;
for(int i=;i<=bl;i++)
{
t*=am;t%=c;
x=find(t);
if(x!=-)
return i*m+x;
}
return -;
} int main()
{
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
while()
{
scanf("%I64d%I64d%I64d",&X,&Z,&K);
if(!X && !Z && !K) return ;
K%=Z;
LL ans=BSGS();
if(ans!=-) printf("%I64d\n",ans+sum);
else printf("No Solution\n");
}
return ;
}
BSGS-二分
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std; typedef long long LL;
const LL N=,Max=(<<)-;
bool bk;
LL X,Z,K,len;
bool vis[];
struct node{
LL d,id,next;
}hash[*Max]; int exgcd(LL a,LL b,LL &x,LL &y)
{
if(b==) {x=,y=;return a;}
LL tx,ty;
LL d=exgcd(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
} void ins(LL d,LL id)
{
LL t=d&Max;
if(!vis[t]) {
vis[t]=;
hash[t].d=d,hash[t].id=id,hash[t].next=-;
return ;
}
for(;hash[t].next!=-;t=hash[t].next))//注意是hash[t].next!=-1
{
if(hash[t].d==d) return;
}
hash[t].next=++len;
hash[len].d=d;hash[len].id=id;hash[len].next=-;
} LL find(LL d)
{
LL t=d&Max;
if(!vis[t]) return -;
for(;t!=-;t=hash[t].next)
{
if(hash[t].d==d) return hash[t].id;
}
return -;
} LL BSGS()
{
LL t,g,x,y,pm,a,b,c,m,k,sum,am;
a=X;b=K;c=Z;k=;sum=;t=%c;
for(int i=;i<=;i++){
if(t==b) return i;
t=t*a%c;
}
while((g=exgcd(X,c,x,y))!=)
{
k=(k*X/g)%c;
c/=g;
if(b%g) return -;
b/=g;
sum++;
}
m=(LL)(ceil((double)sqrt((double)c)));
ins(k,);
t=k;pm=;
for(int i=;i<=m;i++)
{
t=t*a%c,pm=pm*a%c;
ins(t,i);
}
exgcd(pm,c,x,y);
am=x%c+c;
t=b;
for(int i=;i<=m;i++)
{
x=find(t);
if(x!=-) return i*m+x+sum;
t=t*am%c;
}
return -;
} int main()
{
// freopen("a.in","r",stdin);
// freopen("b.out","w",stdout);
while()
{
scanf("%I64d%I64d%I64d",&X,&Z,&K);
if(!X && !Z && !K) return ;
K%=Z;len=Max;
memset(vis,,sizeof(vis));
LL ans=BSGS();
if(ans!=-) printf("%I64d\n",ans);
else printf("No Solution\n");
}
return ;
}
BSGS-Hash