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\)，查一下表看这个数是不是已经被算出来了。

能算出来就能直接输出解了。

[SDOI2011]计算器

#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\)了。

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\n",ans);

	}

	return 0;

}

巴特西

BSGS算法总结

BSGS算法总结

扩展BSGS

最新文章

热门文章