写在前面

在某次集训比赛时遇到了$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$求解就好了