写在前面

开始之前先来两首 \(music\)

<iframe border="0" frameborder="no" height="10" marginheight="0" marginwidth="0" src="https://music.163.com/outchain/player?type=2&id=28590246&auto=0&height=66" width="430"> </iframe> <iframe border="0" frameborder="no" height="86" marginheight="0" marginwidth="0" src="//music.163.com/outchain/player?type=2&id=1826056264&auto=0&height=66" width="330"> </iframe>

简介

BSGS（baby-step giant-step），大步小步算法。

又被称为拔山盖世算法，又被称为北上广深算法。。。。

作用

求解

\[a^x \equiv b \pmod p \]

其中 \(a \perp p\) ，方程的解 \(x\) 满足 $ 0 \leq x < p$ 且数据范围较大，无法直接枚举在 \(O(p)\) 时间内通过。

令

\[x=A \left \lceil \sqrt{p} \right \rceil-B \]

其中

\[0 \leq A,B \leq \left \lceil \sqrt{p} \right \rceil \]

则有

\[a^{\left \lceil \sqrt{p} \right \rceil-B} \equiv b \pmod p \]

由费马小定理得

\[a^{\left \lceil \sqrt{p} \right \rceil} \equiv b \cdot a^B \pmod p \]

我们已知 \(a,b\) 的取值，所以直接枚举 \(B\)，计算 \(b \cdot a^B\) ，将其插入 \(hash\) 表，然后计算 \(a^{A\left \lceil \sqrt{p} \right \rceil}\)，枚举所有 \(A\) 的值，看 \(hash\) 表中是否存在对应的 \(b \cdot a^B\)，即可得到所有的解 \(x\)。

由于 \(A,B\) 均小于 \(\leq \left \lceil \sqrt{p} \right \rceil\) 所以总时间复杂度为 \(O(\sqrt{p})\)，若使用 \(map\) 则多一个 \(\log\) 。

例题

T1

计算

\[a^x \equiv b \pmod p \]

的最小非负整数解，无解时返回 \(-1\) 。

int BSGS(int a, int b, int p)
{
	map<int, int> h;
	b %= p;
	int t = (int)sqrt(p) + 1;
	for (int i = 1; i <= i; i++)
	{
		int tmp = (long long)b * Qpow(a, i, p) % p;
		h[tmp] = i;
	}
	a = Qpow(a, t, p);
	if (!a)
		return !b ? 1 : -1;
	for (int i = 0; i <= t; i++)
	{
		int tmp = Qpow(a, i, p);
		if (h.find(tmp) == h.end())
			return -1;
		else if (i * t - h[tmp] >= 0)
			return i * t - h[tmp];
	}
	return -1;
}

最后

掌握的不是很好哇，如果有错误欢迎向作者提出，蟹蟹！