2023.1.16 [模板]BSGS/exBSGS

全称Boy Step Girl Step

给定一个质数 p，以及一个整数 a，一个整数 b，现在要求你计算一个最小的非负整数 l,

满足\(a^x \equiv b (mod p)\)

算法流程

设t = \(\lceil \sqrt p \rceil\) ,x = i * t - m (0\(\leq\)i\(\leq\)t , 0\(\leq\)m\(\lt\)t - 1)

$a^{i * t - b} \equiv b $(mod p)

\(({a^t})^i \equiv b * a^m\) (mod p)

我们建立一个map,将b * \(a^0\) ~ b * \(a^{t - 1}\) 全部推进去，将值与指数建立映射关系，然后再枚举i，递推算出左式，判断map中是否有值，如果有值则返回答案ans = i * t - map[val]

时间复杂度O(\(\sqrt p\))

inline int BSGS(int a,int b,int p)//a ^ x = b (% p)
{
	map <int,int> q;
	int t = sqrt(p);
	for(int i = 0;i <= t - 1;i++)
		q[(1ll * ksm(a,i,p) * b % p)] = i;
	int c = ksm(a,t,p);
	for(int i = 1;i <= t;i++)
	{
		int now = ksm(c,i,p);
		if(q.find(now) != q.end())
		{
			int x = q[now];
			return i * t - x;
		}
	}
	return -1;
}