浅谈Min_25筛(一看就懂的那种)
2024-09-01 09:51:47
作用
前提:一个积性函数\(F(i)\),要求\(F(P^k),P\in prime\)可以快速计算
实现\(O(\frac{n^{\frac{3}{4}}}{logn})\):\(\sum\limits_{i=1}^nF(i)\)
做法
为了简便运算,定义\(min_i(P)\)为\(i\)的最小质因子
- 定义\(g(n,j)=\sum\limits_{i=1}^n[i\in prime || min_i(P)>P_j]F(i)\)
理解:埃氏筛法筛了\(j\)个质数后剩下的数的\(F(i)\)值之和
\[\begin{aligned}\\
g(n,j)=
\begin{cases}
g(n,j-1)&P_j^2>n\\
g(n,j-1)-F(P_j)[g(\frac{n}{P_j},j-1)-\sum\limits_{i=1}^{j-1}F(P_i)]&P_j^2≤n\\
\end{cases}
\end{aligned}\]
理解\((P_j^2≤n)\):筛完前j-1个质数,筛掉的数除\(P_j\)后一定大于等于\(P_j\)
- 定义\(s(n,j)=\sum\limits_{i=1}^n[min_i(P)≥P_j]F_i\)
\[s(n,j)=g(n,|P|)-\sum\limits_{i=1}^{j-1}F(P_i)+\sum\limits_{k=j}^{P_k^2≤n}\sum\limits_{e=1}^{P_k^{e+1}≤n}s(\frac{n}{P_k^e},k+1)F(P_k^e)+F(P_k^{e+1})\]
理解:满足的质数\(+[min_i(P)≥P_j]\)的合数\((\)枚举最小质因子的次数\()\)
总结
\(\sum\limits_{i=1}^nF(i)=s(n,1)+F(1)\)
例题
咕咕咕
最新文章
- UI-初识君面之理论篇
- C、C++: 引用、指针、实例、内存模型、namespace
- Labview调用Python脚本
- delphi.位操作
- angularJS全选功能实现
- gui学习
- css导航栏
- Python:列表,元组
- 集合框架-Map练习-记录字母出现的次数
- windows平台下VLC2.0.5编译
- hduoj 1077 Catching Fish 求单位圆最多覆盖点个数
- 从NIB中加载VIEW
- php XSS安全过滤代码
- encodeURIComponent() 函数
- linuxDNS
- 10.Odoo产品分析 (二) – 商业板块(5) –日历(1)
- Java读取Properties的几种方法
- React.js 入门与实战之开发适配PC端及移动端新闻头条平台课程上线了
- C++进阶--不让编译器自动生成类函数
- 知物由学 | AI在Facebook清理有害内容上扮演了什么角色?
热门文章
- 【转载】 Asp.Net安全之防止脚本入
- win10重装系统修改信息
- 【已解决】极速迅雷win10闪退解决方案
- 2602978 - [How to] Content Synchronization between SLDs
- Vue指令之`v-for`和`key`属性
- 【坑】select2 模态框中下拉input无法focus
- C# - 配置动态更新
- Java中的File操作总结
- Flutter——Drawer、DrawerHeader、UserAccountsDrawerHeader组件(侧边栏组件)
- Linux:入门基础