[BZOJ3239][BSGS]Discrete Logging

题意

求Ax≡B(mod P)$A^x/equiv B(mod~P)$的最小非负整数解

BSGS裸题

自己推一下：

令x=im+j$x=im+j$ ，m=⌈q√⌉$m=/lceil/sqrt q/rceil$，

AimAj≡B(mod P)$A^{im}A^j/equiv B (mod ~P)$

Aj≡B∗ine(Aim)(mod P)$A^j/equiv B*ine(A^{im})(mod~P)$

已知ine(1)=1$ine(1)=1$

由费马小定理得ine(Aim)=ine(A(i−1)m)∗Ap−1−m mod P$ine(A^{im})=ine(A^{(i-1)m})*A^{p-1-m}~mod~P$

那么ine就可以处理出来了。

把A0...m$A^{0...m}$hash存一下

再求B∗ine(A(1...m)m)$B*ine(A^{(1...m)m})$在hash表中查找。