題意

求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表中查找。