6
12
2015
2

一个很多BSGS算法初学者的误区

感觉标题哪里怪怪的

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

其实就我不知道

 

很多人学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

 

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

 

没了

 

 

 

Category: OI | Tags: | Read Count: 1081
ydc 说:
2015年6月17日 21:53

简直可怕。为什么不能用来做扩展BSGS呢?

ydc 说:
2015年6月17日 21:53

@ydc: 尼玛我是逗逼……求帮忙删掉


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com