kzoacn's Blog

感觉标题哪里怪怪的

以下内容难度偏易，相信很多人都知道，这里只是给不知道的人看的

其实就我不知道

很多人学BSGS都是从网上随便搜一个"baby step giant step",然后找到几个讲解来学(包括我),我一年前好像是看这个学的

似乎90%以上有关BSGS的讲解都是像这么说的:

求

$$a^x=b(mod~prime)$$

设

$$m=\sqrt p,x=im+j$$

于是

$$a^{im}a^j=b(mod~p)$$

$$a^{im}=b(a^{-1})^j(mod~p)$$

枚举j,存到hash表里,再枚举i,遇到的第一个就是答案

但是这里有一个重要的问题许多人都没有注意到,我以前看到的讲解也都没有注意到这个问题

那就是为什么需要求逆

liangjs今天跟我说他是看这里学的BSGS,根本不需要求逆

我们来思考一下为什么我们要令$x=im+j$而不是$x=im-j$呢?

根本没有道理嘛

于是我们令

$$x=im-j$$

于是

$$a^{im}(a^{-1})^j=b(mod~p)$$

$$a^{im}=ba^j(mod~p)$$

真的不需要求逆……

前几天n+e留言说4128只用hash就好了,我还以为是那种$O(n^2p)$的做法……我果然太naive

也就是说这种写法BSGS适用于逆存在但是求逆比较麻烦的情况……嗯……比如说矩阵

各种意义上都能完虐需要逆元的BSGS

写这篇文章用来纪念自己一年都没有注意到的问题

没了