大步小步（bsgs）算法详解

大步小步（Baby Step,Giant Step,BSGS）算法，用来求解类似于$a^x\equiv b(mod$ $p)$的问题，其中$a$，$b$，$p$已经给出，本算法只能解决$p$为素数的问题。

设$m=ceil(sqrt(p))$，$x=i\ast m-j$，则$a^{i\ast m-j}\equiv b(mod$ $p)$，同乘$a^j$可得${(a^m)}^i\equiv b\ast a^j(mod$ $p)$。

接下来考虑枚举所有的$j\in [0,m-1]$，将$b\ast a^j$ $mod$ $p$加入哈希表（可用map）中，再枚举$i\in [0,m]$，计算出${(a^m)}^i$ $mod$ $p$，在哈希表中找出对应的$j$并更新答案，这样$x$就可以算出了，方程的解也可以求出。

时间复杂度$O(sqrt(p))$，$10^{16}$以下都没有问题。

例题：abc270g，