主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
任意模数 C(n,m)
最后更新于 2025-07-31 11:23:20
作者
critnos
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
不太懂数学,有错请指出/kel 首先认为 $\log$ 是小项。有一个比较 trival 的想法。提取模数中 $\le m$ 的素因数,在乘除的时候都把先这些素因数提完。这部分的素因数只有 $O(\log p/\log \log p)$ 个,因此复杂度是 $O(m\log\log\log p)$。 可以发现这里的小素因子提取是很慢的。只需要对不超过 $O(\sqrt{\log p})$ 的质因子用比较高效的方法处理,剩下部分的提取复杂度就是 $O(m)$ 的,最后 crt 合并起来就行。 所以用比较经典的方法,将一个数写作 $p'xa+b$,然后维护一个 $O(\log p)$ 次多项式做倍增点值平移即可。 这样复杂度就是 $O(m)$ 的。 不过看起来利用多项式技术可以进一步优化。对于 $\le \sqrt m$ 的素因数,直接用上面的算法可以 $\tilde O(p')$ 做。对于 $>\sqrt m$ 的素因数和提取完 $\le m$ 的素因数后的部分可以分块后多点求值做。 最后的一个问题是如何提取模数 $\le m$ 的素因数?据说 Pollard-Rho 能够以 $O(\sqrt {p_1})$,$p_1$ 是最小素因子的复杂度给出一组非平凡分解。那这部分也能做到 $\tilde O(\sqrt m)$ 了。可以用快速阶乘算法做到确定性,过程略。
正在渲染内容...
点赞
0
收藏
0