BSGS（北上广深）

算法原理

给出 a，b， p，求最小的非负整数 x，满足，a ^x ≡ b (mod p),其中 p 为质数

时间复杂度

手写哈希表的复杂度：$O(\sqrt{p})$

用 map 的复杂度：$O(\sqrt{p} \log{p})$

代码实现

typedef long long ll;
typedef unsigned long long ull;
typedef long double lb;
inline ll ksc(ull x,ull y,ll p) //O(1)快速乘（防爆long long）
{
	return (x*y-(ull)((lb)x/p*y)*p+p)%p;
}
inline ll fastPow(ll a,ll k,ll p)// a 底数， k 指数， 求 a^k mod p
{
	long long res = 1;
	a%=p;
	while(k > 0)
	{
		if (k & 1) res =ksc(res,a,p);
		a = ksc(a,a,p);
		k >>= 1;
	}
	return res;
}
const int maxn=1e5+7;
struct node
{
	int x,i,pre;
} E[1<<16];
ll cnt,last[maxn];
void add(int i,int x)//插入 hash 表
{
	E[++cnt]=(node)
	{
		i,x,last[i%maxn]
	};
	last[i%maxn]=cnt;
}
int find(int i)   //查哈希表
{
	for (int j=last[i%maxn]; j; j=E[j].pre) if (E[j].x==i) return E[j].i;
	return -1; //-1表示没有找到
}
void init()
{
	cnt=0;
	memset(last,0,sizeof(last));
	memset(E,0,sizeof(E));
}
ll BSGS(ll a,ll b,ll p)// a^x≡b (mod p) 返回x的最小值,无解返回-1
{
    b%=p;
	if(b==1) return 0;//a^0=1
	ll m=sqrt(p)+0.5;
	ll t=b;
	for(int j=0; j<m; ++j)
	{
		add(t,j);
		t=t*a%p;//可能用到快速乘
	}
	ll mi=fastPow(a,m,p),j_hash;
	t=1;
	for(int i=1; i<=m; ++i)
	{
		t=t*mi%p;
		j_hash=find(t);
		if(j_hash!=-1)
		{
			return i*m-j_hash;
		}
	}
	return -1;//无解

}