BSGS算法总结
(BSGS)算法(Baby Step Giant Step)，即大步小步算法，用于解决这样一个问题：
求(y^xequiv z (mod p))的最小正整数解。
前提条件是((y,p)=1)。
我们选定一个大步长(m=sqrt p + 1)，设(x=am+b)，那么显然有(a,bin[0,m))。这样就有(y^{am+b}equiv z (mod p))，就有((y^m)^a=z*y^{-b} (mod p))。
但是这个逆元看起来很不爽，所以我们重新设(x=am-b)，那么就有((y^m)^aequiv z*y^b (mod p))。这时候是(ain[1,m],bin[0.m))。
具体实现方法：
分别计算出(z*y^0,z*y^1...z*y^{m-1})。把算出来的这些东西放到一个表里面，这里用(map)和(hash)都是可以的。（显然(hash)跑得比(map)快到不知道哪里去了）
然后对于(iin[1,m])计算((y^m)^i)，查一下表看这个数是不是已经被算出来了。
能算出来就能直接输出解了。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
map<int,int>M;
int fastpow(int a,int b,int mod)
{
int res=1;
while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
return res;
}
int main()
{
int T=gi(),K=gi();
while (T--)
{
int y=gi(),z=gi(),p=gi();
if (K==1) printf("%d
",fastpow(y,z,p));
if (K==2)
{
if (y%p==0&&z%p) puts("Orz, I cannot find x!");
else printf("%lld
",1ll*fastpow(y,p-2,p)*z%p);
}
if (K==3)
{
if (y%p==0) {puts("Orz, I cannot find x!");continue;}
y%=p;z%=p;
int m=sqrt(p)+1,fg=0;M.clear();
for (int i=0,t=z;i<=m;++i,t=1ll*t*y%p) M[t]=i;
for (int i=1,tt=fastpow(y,m,p),t=tt;i<=m;++i,t=1ll*t*tt%p)
if (M.count(t)) {printf("%d
",i*m-M[t]);fg=1;break;}
if (!fg) puts("Orz, I cannot find x!");
}
}
return 0;
}
扩展BSGS
如果((y,p)
eq 1?)
考虑(y*y^{x-1}+k*p=z)（注意这里是等号不是同余）
根据扩展欧几里得的那套理论，当(z)不是((y,p))的因数的时候就会无解。
否则设(d=(y,p))，那么就会有(frac yd y^{x-1}+k*frac pd=frac zd)。
不断递归下去，直至(d=1)。接下来就可以套用普通的(BSGS)了。
Spoj3105 Mod
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
int gi()
{
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
int y,z,p,ans;map<int,int>M;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int fastpow(int a,int b,int mod)
{
int res=1;
while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
return res;
}
int EX_BSGS()
{
int cnt=0,sum=1;
for (int d=gcd(y,p);d!=1;d=gcd(y,p))
{
if (z%d) return -1;
++cnt,z/=d,p/=d,sum=1ll*sum*y/d%p;
if (z==sum) return cnt;
}
int m=sqrt(p)+1;M.clear();
for (int i=0,t=z;i<=m;++i,t=1ll*t*y%p) M[t]=i;
for (int i=1,tt=fastpow(y,m,p),t=1ll*sum*tt%p;i<=m;++i,t=1ll*t*tt%p)
if (M.count(t)) return i*m+cnt-M[t];
return -1;
}
int main()
{
while (233)
{
y=gi();p=gi();z=gi();
if (y+z+p==0) break;
y%=p;z%=p;ans=EX_BSGS();
if (ans==-1) puts("No Solution");
else printf("%d
",ans);
}
return 0;
}