【POJ2417】Discrete Logging

Description

给定形如$a^xequiv bpmod p$的高次同余方程，求解$x$

Solution

BSGS的模板题

假设$x=i*t-j$，并且$t=lceilsqrt p ceil,0leq jleq {t-1}$

那么方程可化为$a^{i*t-j}equiv bpmod p$

变形，得$(a^t)^iequiv b*a^jpmod p$

对于所有的$jin[0,t-1]$，把$b*a^jmod p$放入哈希表

对于所有的$iin[0,t]$,计算出$(a^t)^imod p$，在哈希表中查找是否存在对应的$j$即可。

时间复杂度为$O(sqrt p)$