【算法】BSGS 算法 – MiNa!

BSGS 算法，即 Baby Steps Giant Steps，又名大小步算法。 拔山盖世算法、北上广深算法 是一种基础的数论算法

给出 a,b,p 三个整数，其中 p 为素数，求一个未知数 x，使 $a^x \equiv b \mod p$

对于上面那个问题，我们可以用 BSGS 解。 怎么解呢？

以下在扯淡：

根据老大爷交换率得出： 没错就是这么简单，化学真奇妙

以上在扯淡：

我们先设 $x=i\times m-j, m=\lceil \sqrt p \rceil$ 那么问题就变成了：$a^{i\times m-j} \equiv b \mod p$ 即：$a^{i\times m}\div a^j \equiv b \mod p$ 即：$a^{i\times m} \equiv a^j\times b \mod p$ 那么我们要求的就是 i 和 j 了，使得上面那个式子成立。 显然，当 $i$更小时，$x$会更小，而且小得更快（相对于 j 的变化而言），即 $i$的改变是大步，而 $j$的改变时小步 根据 BSGS，我们先走小步。 从 0~m 枚举 $j$的取值，用哈希表保存 $a^j\times b \mod p$的值 再从 1~m 枚举 $i$的取值，再用 $a^{i\times m}$的值去哈希表里找，如果哈希表里有这个值，那么这对 $i$和 $j$就是我们要求的了。 而答案就是 $i\times m-j$ 这样做的复杂度是 $O(\sqrt p)$的！

POJ – 2417 Discrete Logging 传送门=￣ω￣=

模板题 但是这题貌似。。。用 map 容易挂，用 map 的 count 函数会超时。。。所以我手动给 j 上 1 再放哈希表里，使用时再减回来，这样就能用 [] 运算符了（更快些）。 数据貌似。。。很水，你枚举 j 从 1 开始也行

代码（目前 vjudge 最短）：