$$a^t\equiv b(mod\ p)$$

时间复杂度$O（\sqrt p）$

欧拉定理：$a^{\phi (p)}\equiv 1(mod\ p)$

所以有：$a^x \equiv a^{x\mod {\phi (p)}}$ (由： $$a^x\equiv a^{x+\phi(p)}$$ 可知)

$$a^x\equiv b(mod\ p)$$

$$x\in[0,\phi(p)-1]$$

放缩一下 $$x\in[0,p]$$

接下来我们将x分成$\sqrt p$ 段

为方便讨论，我们让将上面x视为t

设 $$k=\lceil p \rceil$$ 放缩一下变成 $$k=\lfloor p \rfloor+1$$

$$t=kx-y$$ $$x\in [1,k] \ \ \ \ y\in [0,k-1]$$

所以 $$a^t=a^{kx-y}\equiv b (mod\ p)$$

​ $a^{kx}\equiv b\times a^y (mod\ p)$

对于每个y范围，我们将对应 $b\times a^y (mod\ p)$ 值存到哈希表里面，然后遍历x范围即可

接着0被漏掉了，所以需要特判t=0