Min_25 Sieve 学习笔记
这个东西不是人想的。
解决问题:积性函数前缀和。
适用条件:可以快速计算 \(f(p)\) 的前缀和,\(f(p^k)\) 可以被表示成若干完全积性函数的线性组合(指对应项可以快速组合出来)。
时空复杂度:就当是 \(O(\dfrac{n^\frac{3}{4}}{\log n}+n^{1-\epsilon})-O(\sqrt n)\)。
以下默认 \(f(p)\) 为关于 \(p\) 的单项式,\(p_i\) 为第 \(i\) 个质数。
求质数处的前缀和
我们需要对于每个能被表示成 $\lfloor \dfrac{n}{x}\rfloor $ 的数,求所有在其前的质数 \(p\) 的 \(\sum f(p)\)。注意到一个数的最小质因子小等于 \(\sqrt n\),我们设计一个 dp:\(g_{i,j}\) 表示最小质因子大于 \(p_i\),\([1,j]\) 的所有数的 \(f\) 之和。转移时把最小质因子为 的 \(p_i\) 数的 \(f\) 全部删去,即得转移,注意容斥掉前面的质数的贡献:
\]
这就体现出完全积性的重要性。求和号部分可以在线筛质数的时候预处理出来。第一维显然可以滚动数组优化掉,而对于第二维,$\lfloor \dfrac{n}{x}\rfloor $ 只有 \(O(\sqrt n)\) 个,预处理出来,大于 \(\sqrt n\) 的编号为 \(n/\sqrt n\) 即可。
我们把筛去所有最小质因子后的得到的 dp 数组记为 \(g\)。
求原函数前缀和
设 \(s_{n,i}\) 表示 \([1,n]\) 最小质因子大于 \(p_i\) 的所有数的 \(f\) 之和。枚举最小质因子及其次数,得到转移
\]
根据神奇的复杂度分析,可以直接递归下去做。
最后加上 \(1\) 的贡献。
最新文章
- jenkins 入门教程(下)
- Restive.js – 轻松让网站变成响应式和自适应
- BOM-字节序标记
- OpenStack的Resize和冷迁移代码解析及改进
- Oracle EBS-SQL (WIP-13):检查任务组件未选MRP净值.sql
- 11-3URLTestDemo实例操作完成URL单元测试
- HTML5初步——新的表单元素和属性
- 1951: [Sdoi2010]古文字猪
- [js高手之路]性能优化技巧 - 缓存与函数重载实战
- Switch控件详解
- [MySQL] mysql int后面的数字与前导零填充
- jsp过滤器
- MGR架构~高可用架构细节的梳理
- java中存在三种调用机制
- 前端回顾:2016年 JavaScript 之星
- db2文件系统已满
- ASP.NET Core2利用MassTransit集成RabbitMQ
- Webwork【04】Configuration 详解
- 深入理解 Neutron -- OpenStack 网络实现(3):VXLAN 模式
- MySQL多表联查之ThinkPHP中的实现