BSGS算法总结
\(BSGS\)算法(Baby Step Giant Step)，即大步小步算法，用于解决这样一个问题：
求\(y^x\equiv z\ (mod\ p)\)的最小正整数解。
前提条件是\((y,p)=1\)。
我们选定一个大步长\(m=\sqrt p + 1\)，设\(x=am+b\)，那么显然有\(a,b\in[0,m)\)。这样就有\(y^{am+b}\equiv z\ (mod\ p)\)，就有\((y^m)^a=z*y^{-b}\ (mod\ p)\)。
但是这个逆元看起来很不爽，所以我们重新设\(x=am-b\)，那么就有\((y^m)^a\equiv z*y^b\ (mod\ p)\)。这时候是\(a\in[1,m],b\in[0.m)\)。
具体实现方法：
分别计算出\(z*y^0,z*y^1…z*y^{m-1}\)。把算出来的这些东西放到一个表里面，这里用\(map\)和\(hash\)都是可以的。（显然\(hash\)跑得比\(map\)快到不知道哪里去了）
然后对于\(i\in[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\n",fastpow(y,z,p));
if (K==2)
{
if (y%p==0&&z%p) puts("Orz, I cannot find x!");
else printf("%lld\n",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\n",i*m-M[t]);fg=1;break;}
if (!fg) puts("Orz, I cannot find x!");
}
}
return 0;
}
扩展BSGS
如果\((y,p)\neq 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\)了。
#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\n",ans);
}
return 0;
}
