$$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