BSGS的相关概念

BSGS： $BSGS$ 算法是专门用来求 $a^t \equiv b~(mod~p)$ 这样的高次同余方程的最小正整数解，其中 $a$ 和 $p$ 要求互质，全称叫做 $Baby~Step~Giant~Step$ 算法。

BSGS算法的原理：

$BSGS$ 算法的核心思想是分块来做。

首先根据欧拉定理：$a^{\phi{(p)}} \equiv 1~(mod~p)$，因此可以将 $a^t$ 看作 $a^{k\phi{(p)}+t~mod~\phi{(p)}}$，因此可以得出 $a^t\equiv a^{t~mod~\phi{(p)}}$。因此我们要找的 $t$ 就在 $0 \sim \phi{(p)}-1$ 之间，因此我们就是要在这个范围中找一个最小的 $t$。

然后我们再在 $0 \sim \phi{(p)}-1$ 区间内分块去找 $t$，这里为了方便，直接暴力在 $0 \sim p$ 中找，省去一步求 $\phi{(p)}$ 的步骤。我们取 $k=\lfloor \sqrt{p} \rfloor +1$，然后将 $0 \sim p$ 分成长度为 $k$ 的若干段，大约有 $\sqrt{p}$ 段，此时 $t$ 的所有取值就可以表示成 $kx-y$，其中 $x=\lfloor\frac{t}{k}\rfloor$，因此规定 $x$ 的范围是 $1 \sim k$，$y$ 的范围是 $0 \sim k-1$。当 $x=1,y=k-1$ 时，$t$ 最小为 $1$，当 $x=k,y=0$ 时，$t$ 最大为 $k^2$，因此 $kx-y$ 就可以表示 $1 \sim k^2$ 中的所有数，由于 $k \geq \sqrt{p}$，因此 $k^2 \geq p$，这样我们就还是能枚举到所有可能的值。这里可以发现我们还漏了 $0$ 这个情况，$0$ 我们只需要单独判断一下即可。而为什么 $x$ 不能直接取 $0 \sim k$，这是因为 $x=0$ 时，$t=-y$，此时是可能存在 $t<0$ 的情况的，而我们要求的是 $t$ 的最小正整数解，因此不能考虑负数的情况，所以 $x$ 从 $1$ 开始取，这样能保证不会取到负数，相对方便一些。

接下来我们就是要快速的找出一组 $x,y$ 满足 $a^{kx-y} \equiv b~(mod~p)$，我们这里做一个移项，得到 $a^{kx} \equiv ba^y~(mod~p)$，我们就是要找出一组 $x,y$ 满足这个等式，这里我们可以枚举所有 $x$，对于每个 $x$，看一下是否存在一个 $y$，使得 $a^{kx} \equiv ba^y~(mod~p)$，由于 $y$ 的范围是固定的，因此等式右边所有可能的值也是固定的，那么我们就可以先用哈希表将等式右边的值都存起来，然后从小到大枚举 $x$，对于每个 $x$ 而言，我们查一下哈希表中是否存在一个值是和 $a^{kx}$ 相等的，如果存在，那么我们就找到了一组 $x,y$，并且由于我们是从小到大枚举 $x$ 的，所以找到的一定是最小的解，然后我们就能得到 $t$，就是最终的答案。

注意，我们哈希表中存的是所有 $ba^y~(mod~p)$ 的值，我们并不知道每个值对应的 $y$ 的哪个，因此我们还需要存一下每个值对应的 $y$ 是谁，如果有多个 $y$ 对应一个值，那么我们应该优先保留较大的 $y$，这样才能让 $t$ 尽可能小。

综上所述，就是 $BSGS$ 算法的全部思路，整个算法的时间复杂度是 $O(\sqrt{p})$，用这个思路就能求出高次同余方程的最小正整数解。

扩展BSGS： 扩展 $BSGS$ 算法同样是用来求 $a^t \equiv b~(mod~p)$ 的最小正整数解，但是此时 $a$ 和 $p$ 不一定互质。

扩展BSGS算法的原理：

这里我们同样特判一下如果 $a^0 \equiv b~(mod~p)$，则 $t=0$。

否则，说明 $t \geq 1$，我们设 $a$ 和 $p$ 的最大公约数为 $d$，如果 $d=1$，说明 $a$ 和 $p$ 互质，则直接用普通 $BSGS$ 算法就行了。

如果 $d>1$，说明 $a$ 和 $p$ 不互质，那么我们就不能用普通 $BSGS$ 来求了。此时我们将方程进行转化，$a^t \equiv b~(mod~p)$ 就意味着 $a^t+kp=b$。由于 $a$ 和 $p$ 的最大公约数是 $d$，且 $t \geq 1$，因此 $a^t$ 和 $kp$ 都能整除 $d$，此时如果 $b$ 不能整除 $d$，则一定无解。如果能整除 $d$，则我们将等式两边同时除以 $d$，此时方程变成 $\frac{a}{d} a^{t-1}+k\frac{p}{d}=\frac{b}{d}$，然后我们再将它变回同余方程，得到 $\frac{a}{d} a^{t-1} \equiv \frac{b}{d}~(mod~\frac{p}{d})$。

由于 $a$ 和 $p$ 的最大公约数是 $d$，所以 $\frac{a}{d}$ 和 $\frac{p}{d}$ 就互质了，那么我们就可以用扩展欧几里得算法求出 $\frac{a}{d}$ 关于 $\frac{p}{d}$ 的逆元 $(\frac{a}{d})^{-1}$，则方程变成 $a^{t-1}\equiv \frac{b}{d} (\frac{a}{d})^{-1}~(mod~\frac{p}{d})$。

此时我们令 $t’=t-1,b’=\frac{b}{d}(\frac{a}{d})^{-1},p’=\frac{p}{d}$，那么此时的方程就又变成了一个高次同余方程 $a^{t’}\equiv b’~(mod~p’)$，这就是一个新的高次同余方程问题，此时我们再看一下 $a$ 和 $p’$ 是否互质，如果互质，直接用普通 $BSGS$ 算法来做，如果不互质，则我们可以继续递归处理，直到 $a’$ 和 $p$ 互质为止。由于如果不互质，则 $d$ 是一个 $>1$ 的数，因此整个过程一定会结束，一定有解。

注意，扩展欧几里得算法求出的逆元可能是负数，负数求余也是负的，这样就会导致结果出现偏差，因此每次需要对它进行处理一下保证是正数。