（扩展）BSGS
\(\tt BSGS\)
概念
\(\texttt{BSGS(baby-step giant-step)}\)，即大步小步法，用于求解关于 \(x\) 的形如 $a^x \equiv n(\bmod p) $ 的高次不定方程的最小非负整数解，其中 \(a, b, p\) 为已经给出的常数且 \(a, p\) 互质。
众所周知BSGS=北上广深=拔山盖世
思想
设 \(x = A\lceil \sqrt{p} \rceil - B\)，其中 \(0 \leq A,B \leq \lceil\sqrt{p}\rceil\)
得 \(a^{A \lceil \sqrt{p} \rceil - B} \equiv n(\bmod p)\)
因为 \(a, p\) 互质，所以在模 \(p\) 意义下进行含 \(a\) 的乘除运算没有影响
\(\therefore a^{A \lceil \sqrt{p} \rceil} \equiv na^B(\bmod p)\)
考虑用哈希表预处理出所有 \(na^B\) 的可能取值以及其对应的 \(B\)
再枚举 \(A\) 的所有取值，假设哈希表中存在 \(a^{i \lceil \sqrt{p} \rceil}\) 到 \(t\) 的映射，则最小非负整数解为 \(i \lceil \sqrt{p} \rceil - t\)
如果遍历 \(A\) 的所有取值都无法找到最小非负整数解，则原方程无解
时间复杂度为 \(O(\sqrt{p})\)，用 map 则多 \(log\) 倍常数。
注意 在模 \(p\) 意义下，如果 \(n = 1\) 或 \(p = 1\)，则原方程的最小非负整数解为 \(0\)；如果 \(a = 0\)，若 \(n = 0\)，原方程的最小非负整数解为 \(1\)，反之原方程无解
注意 map 的时间复杂度为 \(log\) 但不会发生哈希冲突，\(\mathcal{O}(1)\) 的unordered_map 可能有哈希冲突。卡常可以考虑手写哈希
模板
P3846 [TJOI2007] 可爱的质数/【模板】BSGS
#include
#include
#include \(\tt exBSGS\)
概念
扩展 \(\texttt{BSGS}\)（\(\tt exBSGS\)），用于求解关于 \(x\) 的形如 \(a^x \equiv n(\bmod p)\) 的高次同余方程的最小非负整数解，其中 \(a, b, p\) 为常数且 \(a, p\) 不一定 互质。
思想
考虑将方程化为某种形式，使得 \(a, p\) 互质。
原方程可以等价地写成 \(a^x + kp = n, k \in \mathbb{Z}\)
设 \(\gcd(a, p) = d\)，根据裴蜀定理知，原方程有解当且仅当 \(d \mid n\)，反之原方程无解。
若原方程有解，则其可进一步化为 \(\frac{a^x}{d} + k \frac{p}{d} = \frac{n}{d}\)
即 \(a^{x - 1} \frac{a}{d} + k \frac{p}{d} = \frac{n}{d}\)
此时 \(a^{x - 1} \rightarrow a^x, \frac{p}{d} \rightarrow p, \frac{n}{d} \rightarrow n\)
递归重复若干次，使得 \(\gcd(a, p) = 1\)
设此时共递归了 \(k\) 次，\(k\) 次递归中的 \(d\) 乘积为 \(d^{\prime}\)
则 \(a^{x - k} \frac{a^k}{d^{\prime}} \equiv \frac{p}{d^{\prime}}(\bmod \frac{n}{d^{\prime}})\ (1)\)
用 \(\tt BSGS\) 求出方程 \(a^{x - k} \equiv \frac{p}{d^{\prime}}(\bmod \frac{n}{d^{\prime}})\) 的最小非负整数解 \(x^{\prime}\)
则此时原方程的最小非负整数解为 \(x^{\prime} + k\)
注意 \((1)\) 式中有系数 \(\frac{a^k}{d^{\prime}}\) 需要乘上，需要作为参数传入 BSGS 函数
详见代码
模板
P4195 【模板】扩展 BSGS/exBSGS
#include
#include
#include