IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    BSGS的严格根号算法

    wyfcyx发表于 2015-08-20 08:02:29
    love 0

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

     



沪ICP备19023445号-2号
友情链接