JDFZOJ的SPJ模板
组合数取模的一点整理0.0

BSGS的严格根号算法

shinbokuow posted @ Aug 20, 2015 08:02:29 AM in Something with tags 数学 BSGS , 1255 阅读

这个算法是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})$.

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter