目录
这玩意这么水的？
线性方程
形如下列形式的方程：
\[\large a^x \equiv b \pmod m
\]
BSGS
简介
BSGS（baby-step giant-step）半死龟速算法，常用于求解离散对数问题。
该算法可以在 \(O(\sqrt{m})\) 的时间内求解 \((a,m)=1\) 时的线性方程。
算法描述
设定一个常量 \(T\)，将 \(x=qT-r\)，其中 \(0\le r< T\)。对原方程进行转化：
\[\large \begin{aligned}
a^{qT-r} &\equiv b &\pmod m\\
a^{qT}&\equiv a^r b &\pmod m
\end{aligned}\]
考虑预处理所有 \(a^{r}b \mod m\) 的值，存到 hash 表/ map 里。求解时枚举 \(q\)，并计算出 \(a^{qT}\)。判断 hash 表/map 里是否出现了 \(a^{qT}\)，出现则说明等式成立，方程有解。
预处理枚举至多 \(T\) 个 \(r\)，复杂度 \(O(T)\)。查询至多 \(\dfrac{m}{T}\) 个 \(a^{qT} \mod m\)，复杂度为 \(O(\dfrac{m}{T})\)。
总复杂度 \(O(\dfrac{m}{T} + T)\)，在 \(T = \sqrt{m}\) 时达到平衡，复杂度为 \(O(\sqrt{m})\)。
正确性
这样构造的 \(x\)，均有 \(x\le m\) 为什么这样一定有解？
考虑欧拉定理，有：
\[a^{\varphi(m)} \equiv 1\ (a\perp m)
\]
由于保证了 \(m\) 为质数，则上式必成立。可知对于一个解 \(x\)，有：
\[a^x\equiv b \Longrightarrow a^{x\mod \varphi(m)}\equiv b \pmod m
\]
则 \(x\le \varphi(m) \le m\) 时必有解。
代码实现
P3846 【模板】BSGS
要输出最小解？有两种方法：
- 存到 map 里，令 \(a^{r}b \mod m\) 映射 \(\min\{ q\}\)。简单暴力，但复杂度多了一个 \(\log\)。
- 改造一下 hash 表，把 \(q\) 一块存进去。
由于枚举的是 q，可保证 \(qT > r\)。第一个枚举到的 \(q\) 即为最小解。
//知识点：BSGS
/*
By:Luckyblock
*/
#include
exBSGS
用于求解 \((a,m)\not=1\) 时的线性方程。
考虑将其转化为 BSGS 的一般形式。发现当 \((a,m)=1\) 时，\(a\) 在 \(\mod m\) 下存在逆元，可令等式右侧出现 \(a\) 的幂次，可以进行 BSGS 算法。
算法描述
设 \(d_1 = (a,m)\)，若 \(d_1 \nmid b\)，则原方程无解。否则令方程两侧同除 \(d_1\)，得到：
\[\dfrac{a}{d_1} \cdot a^{x-1} \equiv \dfrac{b}{d_1} \pmod {\dfrac{m}{d_1}}
\]
若 \((a, \dfrac{m}{d_1}) \not= 1\)，设 \(d_2 = (a, \dfrac{m}{d_1})\)，重复上述步骤。直到 \((a, \dfrac{m}{\prod_{i=1}^{k} d_k}) = 1\) 停止。
记 \(\prod_{i=1}^{k} d_i = D\)，此时方程变为：
\[\dfrac{a^{k}}{D}\cdot a^{x-k}\equiv \dfrac{b}{D} \pmod {\dfrac{m}{D}}
\]
然后就可以直接做 BSGS 了。在枚举 \(a^{qT}\) 判断时乘上常数 \(\dfrac{a^{k}}{D}\) 即可。
注意解 \(x\) 可能 \(\le k\)，在枚举 \(k\) 时判断 \(a^{x-k}\equiv b \pmod m\) 是否存在。注意保证 指数不为负数。
代码实现
P4195 【模板】扩展BSGS
map 会 T。 用 map 跑过去了。
建议改成 hash
//知识点：BSGS
/*
By:Luckyblock
I love Marisa;
but Marisa has died;
*/
#include
例题
稍微化下柿子。
P2485 [SDOI2011]计算器 模板水题。
写在最后
现在是是 2020.8.4 19:38。
我刚刚救出了被困在宿舍楼一下午的学长 cdx。
虽然他水了一下午群打了一下午游戏 看起来很享受的样子。
おめでとう！