BSGS

给定 \(a, b, p\)。求最小非负整数 \(x\) 使得 \(a^x \equiv b \pmod p\)，或报告无解。

保证 \((a,p)=1\)。

首先根据欧拉定理，\(a^x \equiv a^{x \bmod \varphi(p)} \bmod p\)。所以最优的 \(x\) 一定不大于 \(\varphi(p)\)。换一个比较松上限 \(p\)。

不妨先随便找一个数 \(k\)。这个数具体是啥后面再提。

可以证明一定存在一组 \((i,j)\) 使得 \(x=ki-j\) 且 \(j \le k\)（如果 \(j>k\)，那么 \(i'=i-1,j'=j-k\) 同样是一组合法的构造）。那么又可以推出 \(i=\frac{x+j}k\)，而其中 \(\frac jk \le 1\)，\(x \le p\)，所以 \(i \le \frac pk\)。

那么条件变成了 \(a^{ki-j} \equiv b \pmod p\)。同乘 \(a^j\) 得到 \((a^k)^i \equiv ba^j \pmod p\)。现在要判断是否存在一组 \((i, j)\) 满足这个条件且 \(i \ge \frac xk,j \le k\)。

考虑暴力。首先枚举 \(j\)，把所有 \(ba^j \pmod p\) 存储到 map 中。注意如果同一个值对应多个 \(j\) 应保留最大一个。因为我们要最小化 \(ki-j\)。

然后枚举 \(i\)，看一下 map 中是否存在 \((a^k)^i \bmod p\)。如果存在，记录最小的 \(ki-j\)，这个 \(j\) 是通过 map 得到的。

复杂度？其实就是 \(i,j\) 的枚举量，即 \(\mathcal O(\frac pk + k)\)。别忘了这个 \(k\) 的具体值还没有定，现在是时候了。根据均值不等式，\(\frac pk+k\) 在 \(k = \sqrt p\) 时取得最小值 \(2\sqrt p\)。也就是说，\(k\) 取 \(\sqrt p\)，可以得到最优复杂度 \(\mathcal O(\sqrt p)\)。然后还会带一个 map 所以真实复杂度是 \(\mathcal O(\sqrt p \log \sqrt p)\)。不难发现可以用 Hash 表将这个 \(\log\) 去掉，这就不是最重要的问题了。