「学习笔记」min_25筛
前置姿势
其实不看也没关系
用途和限制
在\(\mathrm{O}(\frac{n^{0.75}}{\log n})\)的时间内求出一个积性函数的前缀和。
所求的函数\(\mathbf f(x)\)要满足以下条件:
- \(\mathbf f(p)\)是一个多项式,其中\(p\)是质数
- \(\mathbf f(p^c)\)要能够快速计算。
算法流程
首先我们需要求出对于每一个\(\left\lfloor \frac ni\right\rfloor\)求出\(\sum_{i=1}^x [i \in P] \mathbf f(i)\),其中\(P\)是质数集合。
首先筛出\(\sqrt n\)以内的质数,设\(P_j\)表示从小到大第\(j\)个质数。
设\(\mathbf g(n, j)\)表示所有最小质因子大于\(P_j\)的数加上质数的\(\mathbf f(i)\)的和。
那么\(\mathbf g(n, |P|)\)就是所求。
考虑\(\mathbf g(n, j)\)的转移,分两种情况。
\(P_j^2 > n\)
这个质数不会造成任何影响,于是\(\mathbf g(n, j) = \mathbf g(n, j - 1)\)。
\(P_J^2 \leq n\)
这里我们要考虑筛掉了多少个数字。
那么筛掉的数字中一定含有最小质因子\(P_j\),所以我们考虑减去\(\mathbf g(\frac n{P_j}, j - 1)\),但是这样我们多减了前\(j - 1\)个质数的\(\mathbf f\)之和,所以要加上\(\sum_{i=1}^{j - 1}\mathbf f(P_j) = \mathbf g(P_{j - 1}, j - 1)\)
总结一下就是:
\[
\mathbf g(n,j)=
\begin{cases}
\mathbf g(n,j-1)&P_j^2\gt n\\
\mathbf g(n,j-1)-\mathbf f(P_j)[\mathbf g(\frac{n}{P_j},j-1)-\mathbf g(P_{j - 1}, j - 1)]&P_j^2\leq n
\end{cases}
\]
这里可以滚动数组求一下。(感觉和魔力筛很像呢)
到这里我们发现我们已经对于\(x = \left\lfloor \frac ni\right\rfloor\)求出\(\sum_{i=1}^x [i \in P]\mathbf f(i)\)
设\(\mathbf S(n, j) = \sum_{i=1}^n [\mathrm{minp}(i) \geq P_j]\mathbf f(i)\)
那么最终的答案为\(\mathbf S(n, 1) + 1\)
然后我们将\(n\)以内的数字分为质数和合数
质数部分我们得出答案了,为\(\mathbf g(n, |P|) - \mathbf g(P_{j - 1}, j - 1)\)
考虑合数,其实很简单,考虑枚举最小质因子和其出现次数,然后爆算就可以了。
\[
\mathbf S(n,j)=\mathbf g(n, |P|) - \mathbf g(P_{j - 1}, j - 1)+\sum_{k=j}^{P_k^2\le n}\sum_{e=1}^{P_k^{e+1}\le n}\mathbf S(\frac{n}{P_k^e},k+1)\times \mathbf f(P_k^e)+\mathbf f(P_k^{e+1})
\]
然后就没啦。
最后讲一个东西,就是\(\mathbf S\)不用记忆化。
例题什么的以后再补吧。
最新文章
- Android数据存储之Android 6.0运行时权限下文件存储的思考
- JDBC 练习
- Activityn 生命周期
- Linux 系统常用命令汇总(二) vi 文本编辑
- Orchard官方文档翻译(九) 新增并管理媒体资源
- 配置免安装版JAVA1.7的环境变量
- delphi删除只读文件
- 解决NGINX的WORDPRESS伪静态规则失效的问题
- HDOJ 题目3555 Bomb(数位DP)
- Android 获取唯一标识替代方法
- java中重载一定在一个类里面吗?
- 如何利用docker 构建golang线上部署环境
- Unable to find a constructor to use for type System.Security.Claims.Claim. A class should either have a default constructor
- CSS外边框、边界样式常用组合
- MYSQL总览
- [2019校招] - Java多线程面试题总结
- Java多线程编程——并发编程原理(分布式环境中并发问题)
- AndroidScreenSlide项目切换view动画效果《IT蓝豹》
- jQuery 概述
- Ural 1183 Brackets Sequence(区间DP+记忆化搜索)
热门文章
- 分享基于MemoryCache(内存缓存)的缓存工具类,C# B/S 、C/S项目均可以使用!
- [Go] golang的select多路选择功能
- OO Homework One Notes
- 免费开源ERP Odoo实施指南 连载二:POSTGRESQL概述
- opencv3.2.0图像处理之高斯滤波GaussianBlur API函数
- C# 发送电子邮件源码片段
- 从零学习Fluter(三):Flutter的路由跳转以及state的生命周期
- 章节八、2-火狐的插件TryXPath
- input输入限制,只允许输入数字和“.”,长度不得超过20
- 谈谈你对this对象的理解