BSGS
问题
给定整数 \(a, b, p(0 < a < p, 0 \le b < p, a \perp p)\)，求最小的非负整数 \(x\) 使得
\[a^x \equiv b \pmod p
\]
或判断 \(x\) 是否存在。
过程
思想：根号，折半搜索
令 \(t = \sqrt p + 1,x = At - B\)，则
\[a^x = a^{At-B} \equiv b \pmod p
\]
\[a^x = a^{At-B} \equiv b \pmod p
\]
枚举 \(B \in [0, t]\)，将所有 \(ba^B = val\) 的值用 unordered_map 存，时间 \(o(t)\)。
枚举 \(A \in [1, t]\)，在容器中找 \(a^{At} = val\)，如果存在，说明找到了 \(A, B\)，则 \(x = At - B\)
ExBSGS
问题
\[a^x \equiv b \pmod p (0 < a, 0 \le b)
\]
不要求 \(a \perp p\)。
过程
- 化为不定方程
\[a \times a^{x - 1} \equiv b \pmod p
\]
\[a \times a^{x - 1} + py = b
\]
-
裴蜀定理判无解，令 \(s = \gcd(a, p)\)
-
\(a, p, d\) 都除掉 \(d\)
-
转化为同余方程
\[\frac{a}{d} \times a^{x - 1} \equiv \frac{b}{a} \pmod {\frac{p}{d}}
\]
\[a^{x - 1} \equiv (\frac{b}{a} \times (\frac{a}{d} )^{-1}) \pmod {\frac{p}{d}}
\]
\[a^{x'} \equiv b' \pmod {p'}
\]
- 检查 \(\gcd(a,\frac{p}{d}) = 1\)，如果是，转化为 BSGS 解出 \(x'\)。否则重复执行 1 - 4，直到 \(a \perp p\) 或无解。
要点
- 注意各种边界情况
- 注意 \(x = 0\) 的情况
- 注意是否 \(a \perp p\)
- 注意 \(a = 0\)
- ...
Problem
P3846 【模板】BSGS / [TJOI2007] 可爱的质数 - 洛谷
P4454 [CQOI2018] 破解D-H协议 - 洛谷
读题题
P2485 [SDOI2011] 计算器 - 洛谷
板子杂烩，注意边界，各种边界
P3306 [SDOI2013] 随机数生成器 - 洛谷
题解
相当于有一个一次函数 \(f(x) = ax + b\) 要你求最小的非负整数 \(x\) 使得
\[f^x(s) \equiv t \pmod p
\]
类似 BSGS 的想法
\[f^{At - B}(s) \equiv t \pmod p
\]
由于 \(f\) 是由乘法和加法组成的，所以 \(f^{-B}\) 是由除法和减法组成，不用逆元就可以把 \(B\) 移到右边去。
\[f^{At}(s) \equiv f^B(t) \pmod p
\]
我们还可以用类似于快速幂的方法快速求函数的复合运算，于是我们就用类似于 BSGS 的方法解决了这个问题。
没人觉得乘方和复合很好磕吗？
启示
- 复合运算可以在同余式左右移动，类似乘方，本质加法和乘法
- 快速幂的方法快速求函数的复合运算
- BSGS 思想使用度广
- 边界边界边界