用途

\(O(\sqrt{mod})\)求解方程\(A^x=B\pmod{M}\)。

思想

考虑底数不变时有一种\(O(\sqrt{mod})\)预处理，\(O(1)\)出答案的快速幂算法：将\(A^x\)拆成\(A^{am+b}\)，其中\(m=\sqrt{mod}\)，然后随便预处理一下就好了。

在BSGS算法中，思想也是类似的。设\(A^{am-b}=B\pmod{M}\)，就会有\(A^{am}=B\times A^b\pmod{M}\)。

先\(O(\sqrt{mod})\)预处理出右边所有值丢进hash表中，然后\(O(\sqrt{mod})\)枚举左边，就可以得到答案。

拓展

上面的做法有一个前提：\(\gcd(A,M)=1\)，此时\(A\)才会在模\(M\)意义下有逆元。那么当它们不互质时又该怎么样呢？

数论里面简直是形成一种套路了：当没有逆元时，同时除以\(\gcd\)，于是就开心地互质了。在这里也是一样。

设当前要求解\(A^x=B\pmod{M}\)，且\(\gcd(A,M)=g\)，那么有

然后继续递归/迭代直到互质或B=1即可。

代码

这里以洛谷P4195 【模板】exBSGS为例。

#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifndef ONLINE_JUDGE
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifndef ONLINE_JUDGE
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll ksm(ll x,int y,ll mod){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
ll exgcd(ll a,ll b,ll &x,ll &y){if (!b) return x=1,y=0,a;ll ret=exgcd(b,a%b,y,x);y-=a/b*x;return ret;}
ll inv(ll a,ll mod){ll x,y;exgcd(a,mod,x,y);x=(x%mod+mod)%mod;return x;}
int gcd(int x,int y){ll _,__;return exgcd(x,y,_,__);}

ll BSGS(ll mod,ll A,ll B)
{
	ll m=sqrt(mod)+5;
	unordered_map<ll,int>M;
	for (int i=0,x=1;i<m;++i,x=1ll*x*A%mod) if (x==B) return i; else M[B*x%mod]=i;
	ll X=ksm(A,m,mod);
	for (int i=1,x=X;i<=m;++i,x=1ll*x*X%mod) if (M.count(x)) return i*m-M[x];
	return -1;
}
void exBSGS(ll mod,ll A,ll B)
{
	int g,k=0;
	while ((g=gcd(A,mod))>1)
	{
		if (B==1) return (void)printf("%d\n",k);
		if (B%g) return (void)puts("No Solution");
		mod/=g;B/=g;++k;
		B=B*inv(A/g,mod)%mod;
	}
	ll ret=BSGS(mod,A,B);
	if (ret==-1) return (void)puts("No Solution");
	ret+=k;
	printf("%lld\n",ret);
}

int main()
{
	file();
	ll mod,A,B;
	while (scanf("%lld %lld %lld",&A,&mod,&B),mod+A+B) exBSGS(mod,A,B);
	return 0;
}