这是本文档旧的修订版！
扩展BSGS
原理
求解： $$ a^x\equiv b\pmod p $$ 其中 $a,p$ 不一定互质。
当 $a\perp p$ 时，在模 $p$ 意义下 $a$ 存在逆元，因此可以用 BSGS 算法求解。于是我们想办法让他们变得互质。
具体地，设 $d_1=\gcd(a,p)$。如果 $d_1\nmid b$，则原方程无解。否则我们把方程同时除以 $d_1$，得到 $$ \frac{a}{d_1}\cdot a^{x-1}\equiv\frac{b}{d_1}\pmod{\frac{p}{d_1}} $$ 如果 $a$ 和 $\frac{p}{d_1}$ 仍不互质就再除，设 $d_2=\gcd(a,\frac{p}{d_1})$。如果 $d_2\nmid\frac{b}{d_1}$，则方程无解；否则同时除以 $d_2$ 得到 $$ \frac{a^2}{d_1d_2}\cdot a^{x-2}\equiv\frac{b}{d_1d_2}\pmod{\frac{p}{d_1d_2}} $$ 同理，这样不停地判断下去。直到 $a\perp \frac{p}{d_1d_2\cdots d_k}$。
记 $D=\prod_{i=1}^k d_i$，于是方程就变成了这样： $$ \frac{a^k}{D}\cdot a^{x-k}\equiv\frac{b}{D}\pmod{\frac p D} $$ 由于 $a\perp \frac p D$，于是推出 $\frac{a^k}{D}\perp\frac p D$。这样 $\frac{a^k}{D}$ 就有逆元了，于是把它丢到方程右边，这就是一个普通的 BSGS 问题了，于是求解 $x-k$ 后再加上 $k$ 就是原方程的解了。
注意，不排除解小于等于 $k$ 的情况，所以在消因子之前做一下 $\Theta(k)$ 枚举，直接验证 $a^i\equiv b\pmod p$，这样就能避免这种情况。
例题
题意：给定 $a,p,b$，求满足 $a^x\equiv b\pmod p$ 的最小自然数 $x$。
题解：模板题。
代码：`qwq` 对应原理中的 $d_i$，`qaq` 对应原理中的 $\frac{a^k}{D}$。
