Min_25 太神仙了！
据说这个筛法的复杂度是 O(n3/4logn) 或 Θ(n1−ϵ) 的。（别问我 ϵ 是啥，问就不知道
本质上其实是扩展埃筛。
感谢 chd 哥哥让我学会 Min_25 筛！（@Trisolaris
筛啥用的？
积性函数前缀和，不然用着干啥（
要求被筛的函数 f 在质数 p 处的值 f(p) 的值为一个关于 p 的低次多项式，在 pc 处的值 f(pc) 可以快速计算。
记号
- P 表示全体质数的集合。
- 本文一般默认 p∈P。
- pk 为第 k 小的质数。特别地，p0=1。
- lpf(n) 表示 n 的最小质因子（即 Least Prime Factor
- FP=∑2≤p≤nf(p)
- Fk=n∑i=2[pk≤lpf(i)]f(i)
怎么筛？
假设我们已经算出了所有 F，可以发现答案就是 F1(n)+f(1)=F1(n)+1。
求 F
枚举最小质因子及其指数可得 Fk(n)=∑k≤i,p2i≤n∑c≥1,pci≤nf(pci)([c>1]+Fi+1(⌊npci⌋))+∑k≤i,pi≤nf(pi)=∑k≤i,p2i≤n∑c≥1,pci≤nf(pci)([c>1]+Fi+1(⌊npci⌋))+FP(n)−FP(pk−1)=∑k≤i,p2i≤n∑c≥1,pc+1i≤n(f(pci)Fi+1(⌊npci⌋)+f(pc+1i))+FP(n)−FP(pk−1)
看起来非常的迷，接受不了。
第一个等号后，第一个和式的意思就是枚举最小质因子，并且显然每个合数的最小质因子一定在 √n 内。
第二项是补回质数的贡献，因为 c=1 时没有计 f(pc)=f(p) 的贡献。
第二个等号后只是把第二项根据定义拆成前缀和的形式。
最后一个等号比较奇怪。
注意到若 pci≤n<pc+1i，显然有 ⌊npci⌋<pi+1，故 Fi+1(⌊npci⌋)=0。
假设已经求得了所有 FP，现在理论上有两种方法计算 F，根据上式直接递归就是其中一种。
Yet Another F
话说其实 Min_25 筛有无数种实现方式……重要的是埃氏筛的思想。
所以我也不知道从哪里看来的改成递推形式要换 F 的定义（逃
（如果不换的话也从上式能导出比较显然的递推式，不过也许这种更好写？
令 Fk(n)=n∑i=2[pk≤lpf(i)∨i∈P]f(i)
易知答案同样为 F1(n)+1。
考虑一个递推式 Fk(n)=Fk+1(n)+∑c≥1,pc+1k≤n(f(pck)(Fk+1(⌊npc⌋)−FP(pk))+f(pc+1k))
于是同样地枚举最小质因子即可。
边界条件为 Fπ(√n)+1(n)=FP(n)。
似乎因为指数不会很大所以复杂度仍然是 O(n3/4logn)。
求 f 在质数处的值
根据递推式可以发现实际上需要用到的 FP 只有形如 ⌊nx⌋ 的 O(√n) 处。
根据条件，f(p) 可以写作 ∑aipi。
故我们可以分别讨论每一项的贡献。
设 Gk,s(n)=n∑i=1[pk<lpf(i)∨i∈P]is。
熟悉埃筛的话，你会发现这相当于是埃筛筛了 k 轮后剩下的数的 s 次方之和。
最后我们想要的实际上就是 Gπ(√n),s(n)，其中 π(√n) 表示 |{p:p≤√n}|。
因为一个合数的最小质因子肯定不会超过 √n。
考虑转移。
对于 n<p2k，并没有筛掉新的数，故直接转移即可。
对于 p2k≤n，筛掉的数显然有质因子 pk，故减去 pskGk−1,s(⌊npk⌋)。
然鹅我们筛掉的应该是 lpf(m)=pk 的 m，故要考虑 lpf(m)<pk 的 m 的贡献。
实际上就是加回 pskGk−1,s(pk−1)。
综上所述，有 Gk,s(n)=Gk−1,s−[p2k≤n]psk(Gk−1,s(⌊npk⌋)−Gk−1,s(pk−1))
复杂度？
并不会证明，由论文可得求 Fk 的复杂度为 Θ(n1−ϵ)（第一种方法）。
求 FP 的复杂度为 O(n3/4logn)（第二种方法的复杂度也长这样）。
一些提示
很多东西可以直接欧拉筛预处理，至于是啥，自己想想。
例题 - LibreOJ 6053.简单的函数
注意到质数除了 2 都是奇数，故 f(p)=p−1+2[p=2]。
于是有 G0,0(n)=−n+1,G0,1=(n+2)(n−1)2。
然后对 2 讨论一下即可。
递归写法的代码见 https://www.alpha1022.me/articles/loj-6053.htm
Yet Another F 中的写法代码：
1 |
|