BSGS 与 exBSGS 算法学习笔记
acmpGu
·
·
算法·理论
什么是 BSGS？
BSGS 是用来解决高次同余方程模数是质数的一种算法。
高次同余方程
已知整数 a, b, p，其中 p 为质数，求最小的非负整数 x，使得 a^x \equiv b \pmod{p}。
因为 p 是质数，根据费马小定理，a^{p-1} \equiv 1 \pmod{p}。又知道 a^0 \equiv 1 \pmod{p}，所以幂有长度不超过 p 的循环节。暴力枚举 x < p 即可。
但是如果 p 达到了 10^9 级别怎么办？
引入 BSGS
BSGS = Baby Steps Giant Steps，可以音译为北上广深，拔山盖世（你也可以音译为爆杀高三），只要见到别不认识就行。
BSGS 算法的思想是 meet in the middle，时间复杂度 O(\sqrt{p})。
设 x = im - j（x 相当于被除数，m 相当于除数，i 相当于商，j 相当于负余数），其中 m = \left\lceil \sqrt{p} \right\rceil，这样原式变为 a^{im-j} \equiv b \pmod{p}，可以进一步变形得到：
(a^m)^i \equiv b \cdot a^j \pmod{p}
$i$ 的取值范围是 $[1, m]$，可以直接枚举等号左边，到哈希表中去找是否有相同的值。找到的第一个相等的 $i$，对应的 $im - j$ 就是最小的 $x$。
### BSGS 例题
**[P3846 [TJOI2007] 可爱的质数/【模板】BSGS](https://www.luogu.com.cn/problem/P3846)**
模板题，按照正常 BSGS 的思路写代码就可以。
[代码](https://www.luogu.com.cn/paste/z2k4ywz8)
---
**[P2485 [SDOI2011]计算器](https://www.luogu.com.cn/problem/P2485)**
$K = 1$ 时：直接快速幂算出 $y^z \bmod p$；
$K = 2$ 时：费马小定理算出 $xy \equiv 1 \pmod{p}$ 时 $x$ 的值，将结果乘上 $z$ 即可，注意当 $p \mid y$ 且 $z \nmid y$ 时无解；
$K = 3$ 时，用 BSGS 求出 $x$，注意特判 $p \mid y$ 的情况。
[代码](https://www.luogu.com.cn/paste/4g5szkwj)
---
**[P4454 [CQOI2018]破解D-H协议](https://www.luogu.com.cn/problem/P4454)**
这题说了一大堆，其实一半都没用，这道题的意思就是求出 $A = g^a \bmod P$ 的 $a$，然后求出 $K = B^a \bmod P$ 的 $K$ 或者 求出 $B = g^b \bmod P$ 的 $b$，然后求出 $K = A^b \bmod P$ 的 $K$。
那么我们可以用 BSGS 求出 $a$ 或 $b$，然后快速幂求出 $K$。
[代码](https://www.luogu.com.cn/paste/6eb16vo4)
---
**[P4884 多少个 1？](https://www.luogu.com.cn/problem/P4884)**
$$\begin{matrix}\underbrace{111 \cdots 11}\\N \text{个} 1\end{matrix} \equiv K \pmod{m}$$
$$\begin{matrix}\underbrace{999 \cdots 99}\\N \text{个} 9\end{matrix} \equiv 9K \pmod{m}$$
$$10^N \equiv 9K + 1 \pmod{m}$$
现在我们就可以用正常的 BSGS 求出 $N_{min}$ 了，但是这里需要注意，由于 $m$ 比较大，`long long` 乘法有溢出风险，所以要用龟速乘。
[代码](https://www.luogu.com.cn/paste/7zh6orv5)
---
## 什么是 exBSGS
exBSGS 是用来解决高次同余方程**通用**的一种算法。
### 引入 exGSGS
**exBSGS = 扩展 BSGS 算法**，针对 $p$ 可能不是质数的情况。
无解的判定条件是：$(a, p) \nmid b$ 且 $b \neq 1$。
对于式子：
$$a^x \equiv b \pmod{p}, g = (a, p)$$
两边同时除掉 $g$：
$$a^{x-1} \cdot \frac{a}{g} \equiv \frac{b}{g} \pmod{\frac{p}{g}}$$
设 $a' = \frac{a}{g}, b' = \frac{b}{g}, p' = \frac{p}{g}$。
原式变成：
$$a^{x-1} \cdot a' \equiv b' \pmod{p'}$$
一直这样迭代下去，直到无解或者 $a', p'$ 互质即可。
最终原式变为（设 $M = \prod\limits_{i=1}^kg_i$）：
$$a^{x-k} \cdot \frac{a^k}{M} \equiv \frac{b}{M} \pmod{\frac{p}{M}}$$
此时 $\frac{a^k}{M}$ 与 $\frac{p}{M}$ 互质，可以用正常的 BSGS 解决。
### exBSGS 例题
**[P4195 【模板】扩展 BSGS/exBSGS](https://www.luogu.com.cn/problem/P4195)**
模板题，按照引入中的 exBSGS 的思路加上正常 BSGS 的思路写代码就可以。
[代码](https://www.luogu.com.cn/paste/utiv1x10)
> 关于 BSGS 与 exBSGS 的学习笔记就到这里啦！持续更新……