BSGS&exBSGS 学习笔记

写在前面

在某次集训比赛时遇到了$esBSGS$毒瘤题,被大佬们暴捶,过了一个多月本蒟蒻才开始学习$BSGS\text{&}exBSGS$

BSGS

$BabyStepGiantStep$算法,即大步小步算法,缩写为$BSGS$,而$esBSGS$,顾名思义,就是$BSGS$的拓展。

$BSGS$用来解决如下问题:

给定一个质数$P(2\leq P < 2^{31})$,以及一个整数$Y(2\leq A < P)$,一个整数$Z(2\leq Z <P)$,求最小的$X$,满足$Y^X \equiv Z \mod P$

例题:Luogu P3846 [TJOI2007]可爱的质数

算法思路如下:

设$m=\sqrt{P}$,$X=a\times m-b$,$a\in [0,m+1]$,$n \in [0,m)$。

那么$Y^{a \times m-b}\equiv Z \mod P$

$Y^{a\times m}\equiv Z \times Y^{b} \mod P$,

所以只要$O(m)$记录一下右边的值,然后枚举左边,查表即可。

exBSGS

$exBSGS$顾名思义(大雾),就是$BSGS$的拓展。适用于解决如下问题:

给定一个整数$P(2\leq P < 2^{31})$,以及一个整数$Y(2\leq A < P)$,一个整数$Z(2\leq Z <P)$,求最小的$X$,满足$Y^X \equiv Z \mod P$

例题:Luogu P4195 【模板】exBSGS/Spoj3105 Mod

算法思路如下:

对于$gcd(y, p)\ne1$怎么办?

我们把它写成$y\times y^{x-1}+k\times p=z, k\in Z$的形式

根据$exgcd$的理论
那么如果$gcd(y,p)$不是$z$的约数就不会有解

设$d=gcd(y,p)$
那么$\frac{y}{d}\times y^{x-1}+k\times \frac{p}{d}=\frac{z}{d}$

递归到$d=1$
设之间的所有的$d$乘积为$g$,递归$c$次
令$x’=x-c, p’=\frac{p}{g},z’=\frac{z}{g}$
那么$y^{x’}\times \frac{y^c}{g}=z'(mod \ p’)$

那么$BSGS$求解就好了

暂无评论

发送评论


				
上一篇
下一篇