basic

BSGS算法英文名叫“baby-step giant-step”，又称“大步小步算法”。

这个算法听名字似乎是个随机化算法，但实际上是数论算法。

具体地，这个算法解决的是 $a^x \equiv b \pmod{p}$ 的解，其中 $a$、$b$、$p$ 是已知的（$0 \leq a,b<p$，保证 $\gcd(a,p)=1$），$x$ 是要求的。

这个算法甚至可以求出所有的 $x$，但为了好讲，我们先考虑如何求出是否有解，以下代码中YES就代表确定有解了。

force algorithm

首先，有一个暴力算法：

rep(x, 0, INF)
    if(ksm(a, x, p) == b)
        YES

但这个算法是 $O(\infty)$ 的，我们考虑优化。

optimization algorithm 1

我们考虑 $x$ 的上界，根据欧拉定理，$a^{\varphi(p)} \equiv 1 \pmod{p}$，我们就可以确定，$x$ 的上界就是 $\varphi(p)$（准确来说减 $1$ 也彳亍），因为如果 $x>\varphi(p)$，那么 $a^x$ 就等于 $a^{x-\varphi(p)}$，也就成为了一个循环，所以上界就是 $\varphi(p)$。

由于 $\varphi(p)<p$，所以可以把 $p$ 当做是质数，$x$ 的上界也就是 $p-1$ 了。

所以：

rep(x, 0, p - 1)
    if(ksm(a, x, p) == b)
        YES

optimization algorithm 2 (BSGS)

但这个算法还是可能会TLE，我们继续考虑优化

我们定义 $q=\left\lceil \sqrt{p} \right\rceil$，那么我们其实就可以把 $x$ 表示为 $q$ 进制下的两位数，具体地，我们把 $x$ 表示为了 $Aq+B$（$0 \leq A,B<q$），然后上述公式就可以化成 $a^{Aq+B} \equiv b \pmod{p}$，即 $a^{Aq} \times a^B \equiv b \pmod{p}$。

但此时仍然不好求答案，我们继续转化，我们考虑移项，变成 $a^{Aq} \equiv b \times a^{-B} \pmod{p}$。

但这个 $a^{-B}$ 不好看，我们换一下。

我们从最初公式开始修改：

$a^{Aq-B} \equiv b \pmod{p}$（$0 \leq A \leq q \land 0 \leq B<q$）

变化后：

$a^{Aq} \times a^{-B} \equiv b \pmod{p}$

移项后：

$a^{Aq} \equiv b \times a^B \pmod{p}$

但此时我们发现还是没有显著优化效果啊，代码还是 $O(p)$ 的：

rep(A, 0, q)
    rep(B, 0, q - 1)
        if(ksm(a, A * q, p) == b * ksm(a, B, p) % p)
            YES

但我们发现，两重循环枚举的 $A$ 和 $B$ 是独立的，我们可以使用类似于双向搜索的思想变化成：

set<LL> s;
rep(A, 0, q)
    s.insert(ksm(a, A * q, p));
rep(B, 0, q - 1)
    if(s.count(b * ksm(a, B, p) % p))
        YES

所以这个算法复杂度就变成了 $O(q \times \log q)$，即 $O(\sqrt{p} \times \log \sqrt{p})$，在 $p \leq 2 \times 10^9$ 左右的数据范围下是稳稳地过的。

summary and exdend

其实BSGS就是用的（类似于）拆分的方法，把 $x$ 拆成用两个数 $A$、$B$（$A,B$ 在根号范围）来表示，然后发现 $A$ 和 $B$ 的枚举独立，然后才有这个优化。

最开始的时候，提到有求出所有的 $x$ 的方法，其实也就是小改动一下，把set<LL>换成map<LL,bs<LL>>即可，代码很相似。

不过，让求出所有的 $x$ 的题目必须要保证解的数量，但求出 $x$ 的数量的题目就不需要，对于求数量的题目，要换成map<LL,LL>来存。

exBSGS

上面说要保证 $\gcd(a,p)=1$，但如果不保证呢？就需要用到exBSGS。

其实exBSGS也很简单，首先我们设 $d=\gcd(a,p)$，那么显然在 $d|b$ 的时候，方程才有解。

然后我们考虑转化。

我们把方程直接转化为 $\dfrac{a^x}{d} \equiv \dfrac{b}{d} ~ \left( \bmod~\dfrac{p}{d} \right)$，即 $\dfrac{a}{d} \times a^{x-1} \equiv \dfrac{b}{d} ~ \left( \bmod~\dfrac{p}{d} \right)$。

但此时的 $a$ 和 $\dfrac{p}{d}$ 也不一定互质，我们需要继续进行操作。

我们设进行了 $k$ 次操作，第 $i$ 次操作前，$d$ 的值为 $d_i$，那么其实最终的方程就是：

$\dfrac{a^k}{d_1 \times d_2 \times d_3 \times \dots \times d_k} \times a^{x-k} \equiv \dfrac{b}{d_1 \times d_2 \times d_3 \times \dots \times d_k} ~ \left( \bmod~\dfrac{p}{d_1 \times d_2 \times d_3 \times \dots \times d_k} \right)$。

此时直接用类似于BSGS的方法求即可。