SP22549 DIVFACT4 - Divisors of factorial (extreme) 发表于 2022-07-25 分类于 OI 本文字数: 403 阅读时长 ≈ 1 分钟 标签: Min_25筛 LuoGu: SP22549 DIVFACT4 - Divisors of factorial (extreme) SPOJ: DIVFACT4 - Divisors of factorial (extreme) 对于一个质数 p ,其指数为 ∑k⌊npk⌋ 。考虑对于 p≤n ,可以暴力在 nlogn 的时间内完成,可以接受。对于 p>n ,贡献只有 ⌊np⌋ 。考虑数论分块,对于每个 j=⌊ni⌋ ,我们需要计算出 ∑k=2j[k∈Prime] 。可以用 Min_25 筛。 查看代码 1 相关文章 Min_25 筛 模板 SP19975 APS2 - Amazing Prime Sequence (hard) SP34096 DIVCNTK - Counting Divisors (general) 本文作者: RuSun 本文链接: https://rusunoi.github.io/post/SP22549/ 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
Gitalk 加载中 ...