BSGS的严格根号算法
这个算法是jkxing脑补出来的,ozorzzz...
现在我们要求一个最小的$x$满足$a^x\equiv{b}\pmod{c}$.
假设满足$(a,c)=1$.
不难证明若存在可行解必定有$x<c$.
我们令$m=\lceil\sqrt{c}\rceil$,首先预处理出$a^0,a^1,...a^{m-1}$在mod$c$意义下的值并存入hash表.
然后我们从小到大枚举$i$,对于每个$i$,我们考虑$(a^m)^i\times{y}\equiv{b}\pmod{c}$,一般情况下我们需要利用拓展Euclid算法求出$y$,然后在hash表中查找.
这个算法是$O(\sqrt{n}logn)$的.
事实上每次将得到的$y$乘上$a^m$的逆元就可以得到下一个$y$了,所以只需预先求出$a^m$的逆元,这样就变成了$O(\sqrt{n})$.
评论 (0)