首页 > 代码库 > BSGS算法_Baby steps giant steps算法（无扩展）最强详解，你从未见过的详细
BSGS算法_Baby steps giant steps算法（无扩展）最强详解，你从未见过的详细
Baby Steps-Varsity
Giant Step-Astronauts(May‘n?椎名慶治)
阅读时可以听听这两首歌，加深对这个算法的理解。（Baby steps少女时代翻唱过，这个原唱反而不是很有名……Giant Step就比较碉，是一个假面骑士片的插曲，由超碉的May‘n和一个人建立的临时组合唱的，怕不怕）
这个主要是用来解决这个题：
A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。
我在网上看了好多介绍，觉得他们写得都不够碉，我看不懂…于是我也来写一发。
先把x=i*m+j，其中m=ceil(sqrt(C))，（ceil是向上取整）。
这样原式就变为A^(i*m+j)=B(mod C)，
再变为A^j=B*A^(-m*i) (mod C)，
先循环j=0~(C-1)，把（A^j,j)加入hash表中，这个就是Baby Steps（现在可以播放Baby Steps-Varsity了）。然后我们再枚举等号右边，从hash表中找看看有没有，有的话就得到了一组i j，返回x=i*m+j，得到解。（原理我还没懂……懂了我会贴上来）
所以，接下来要解决的就是枚举B*A^(-m*i) (mod C)这一步。A^(-m*i)相当于1/(A^(m*i))，里面有除法，在mod里不能直接用除法，这时候我们就要求逆元。
/*百度百科：
对xA+yB=z，
变成这样xA = z - yB，取B=C（C就是我们要mod的那个）
推导出 xA % C = z %C
只要 z%C==1 时,就可以求出A的逆元x
但用exgcd求完，x可能是负数，还需要这样一下：x=(x%C+C)%C
//--exgcd介绍完毕--
再看我们的题目，
exgcd(A^(m*i) , C)=z，当C是质数的时候z肯定为1，这样exgcd求得的x就是逆元了。
因为x就是A^(m*i)的逆元，P/(A^(m*i))=P*x，所以
B*A^(-m*i) = B/(A^(m*i)) = B*x(mod C)
这样我们的式子A^j=B*A^(-m*i) (mod C)的等号右边就有了，就是B*x，就问你怕不怕！
枚举i，求出右边在hash里找，找到了就返回，无敌！