ExBSGS

前置知识

BSGS（北上广深）

算法原理

时间复杂度 :$O(\sqrt{n}\;log{n})$

代码实现

int BSGS(int a,int b,int p,int k)// a^x≡b (mod p) 返回x的最小值,无解返回-1
{
	map<int,int> hs;
	int m=sqrt(p)+1,t=1;
	for(int j=1; j<=m; ++j)
	{
		t=1ll*t*a%p;//可能用到快速乘
		hs[1ll*t*b%p]=j;
	}
	k=1ll*k*t%p;
	for(int i=1; i<=m; ++i)
	{
		int j = hs.count(k) ? hs[k] : -1;
		if(j!=-1&& i * m - j >= 0)
		{
			return i*m-j;
		}
		k=1ll*k*t%p;

	}
	return -1;//无解

}
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
int ExBSGS(int a,int b,int p)
{
	if(b==1||p==1) return 0;
	int d=gcd(a,p),k=1,cnt=0;
	while(d!=1)
	{
		if(b%d) return -1;
		cnt++;
		b/=d,p/=d;
		k=1ll*k*a/d%p;
		if(k==b) return cnt;
		d=gcd(a,p);
	}
	int res=BSGS(a,b,p,k);
	if(res<0) return -1;
	return res+cnt;
}

参考博客

BSGS、EXBSGS