BSGS
用途：给定形如$A^x equiv z (mod p)$(p为质数)的式子，给定A、z、p,求满足条件的x的最小值。
解法：
考虑暴力，暴力枚举0到p-1并验证，复杂度O(n)。
考虑优化：考虑通过预处理来加速算法。
$$A^x equiv z (mod p)$$
设$c$=$sqrt{p}$，也就是我们的块大小，
$$A^{ic+j} equiv z (mod p)$$
$$A^j equiv z*A^{-ic} (mod p)$$
我们把$1$到$c$的$A^i$存入hash池中，这样我们每次枚举$A^{-ic}*z$,在hash池中查询，这样就可以同时检验$1--c$个值是否出现。
具体来说就是如果查询到一个值，设其为T,则
$$A^T equiv z*A^{-ic} (mod p)$$
x为T+ic。
复杂度O($sqrt{n}$)。
优化的地方在于我们一次可以同时比较$sqrt{n}$个值。
拓展BSGS：
$$A^x equiv z (mod p)$$
同时两边取t=gcd(A,P)。
原式 ：
$$A^{x-1}*frac{A}{t} * t equiv frac{z}{t} * t (mod frac{p}{t} * t)$$
则，现在原式变成：
$$ A^{x-1}*frac{A}{t} equiv frac{z}{t} (mod *frac{p}{t})$$
这个过程会一直进行直到A、P互质。
显然，当z在中途无法被除尽时，就是无解。
现在，原式变成：
$$ A^{x-k}*C equiv T (mod P)$$
由于$C$是由若干个A除若干个其他因子得到，$C$与$P$必然也互质。
用欧拉定理把$C$的逆元乘到右边，然后再用普通BSGS即可。
注意最后算答案的时候$A$是减了$K$个的，我们把$K$加上就行。