积性函数求和
psoet
·
·
个人记录
这篇文章作为坑被藏了几个月，然后发现没啥好更的。
积性函数，狄利克雷卷积
如果函数f满足a \perp b \Rightarrow f(ab) = f(a)f(b)则称f是积性函数。
数论函数f和g的狄利克雷卷积(f*g)(n) = \sum_{xy = n}f(x)g(y)。
狄利克雷卷积满足交换律、结合律和分配律。在狄利克雷卷积意义下的单位元是\epsilon(n) = [n = 1]。对于函数f，总是能构造出来唯一的函数g满足f*g = \epsilon，因为我们可以从小到大确定每个位置的取值。
既然有逆元，我们就能定义狄利克雷除法：h = f / g是使g * h = f成立的函数。
狄利克雷卷积在所有的积性函数内有封闭性：如果f和g均是积性函数，那么f*g，f/g也都是积性函数。这个通过定义算就好了。
定义点积f \cdot g是f和g的对应位置相乘，那么对于完全积性函数f和数论函数g和h，我们有(f\cdot g)*(f\cdot h) = f\cdot (g*h)。
杜教筛，Bell级数
假设我们要算积性函数f的前缀和。如果f = g / h，g和h的前缀和都很好求，那么我们就有
\sum_{i=1}^ng(i) = \sum_{i=1}^nh(i)\sum_{j=1}^{\lfloor{n\over i}\rfloor}f(j)
S_f(n) = S_g(n)-\sum_{i=2}^mh(i)S_f({\lfloor{n\over i}\rfloor})
所有的n都在整除分块范围内（此后我们简称之为“块内")，可以递推算S_f。
考虑这个东西的复杂度。在某一个n处计算的复杂度是O(\sqrt n)。我们设要算N的所有块内取值，那么复杂度是
O(\sum_{i=1}^{\sqrt N}\sqrt i+\sum_{i=1}^{\sqrt N}\sqrt{N\over i})=O(N^{3/4})
但是还能做到更好，我们设对于n \leq N^c部分直接线筛，那么现在的复杂度是
O(N^c + \sum_{i=1}^{N^{1-c}}\sqrt{N\over i}) = O(N^c + N^{1-c/2}) = O(N^{2/3})
注意到如果$f$和$g$在块内取值已知，那么$f*g$也很好求。所以，已知$f$和$g$，我们可以推出$f*g$和$f/g$。
显然杜教筛最大的难点在于构造一个可以筛的积性函数$f$和$g$。我们想要一个比较好的可以刻画积性函数性质的工具。
定义一个数论函数$f$模质数$p$意义下的Bell级数
$$F_p(x) = \sum_{i \geq 0}f(p^i)x^i$$
对于绝大多数的情况，对于各个$p$，$F_p$的形式都是相同的。（如果$f$关于各个$p$不对称，可以料想到不会有什么很好的结果。）于是，我们建立了一个数论函数和幂级数的对应关系。
积性函数的乘除放在Bell级数上都是成立的，于是我们按凑Bell级数的方式对应就能凑出杜教筛。
（加减则不行，因为加减之后就不是积性函数了）
例子：
$$\epsilon \rightarrow 1$$
$$I\rightarrow {1\over1-x}$$
$$id^k \rightarrow {1\over 1-p^kx}$$
$$\mu \rightarrow 1-x$$
$$\varphi \rightarrow {1-x\over 1-px}$$
有趣的是，对于刘维尔函数$\lambda$，
$$\lambda \rightarrow {1\over 1+x}={1\over 1-x^2}/I$$
于是，$\lambda * I$在且只在完全平方数处是1.
还有一个值得讨论的东西：积性函数和完全积性函数的点积。
$f$点积$id^k$相当于把$x$替换成$xp^k$。
例子：
$$\mu\cdot id^k \rightarrow 1-p^k x$$
$$\varphi \cdot id^k \rightarrow {1-p^kx \over 1-p^{k+1}x}$$
结合$id^k$的Bell级数，这些都是可以筛的。
### Powerful Number
定义powerful number是所有质因子出现次数至少是2的数。
结论：$N$以内powerful number的个数是$O(\sqrt n)$。
这是因为，显然一个powerful number可以写成$a^2b^3$，总数显然是$\sum_i \sqrt{n \over i^3} = O(\sqrt n)$。
对于一个积性函数$F$，我们构造另一个积性函数$G$，满足$\forall p,F(p) = G(p)$，令$H = F/G$。
可以发现，$F(p) = H(p)G(1)+H(1)G(p) = H(p)+G(p)$，所以$H(p) = 0$，所以$H$只在powerful number处有值。如果筛出$G$在块内的值就能枚举$H(i)$算贡献了。
求$H$可以用狄利克雷除法的定义，经过一些琐碎的工作可以得出复杂度不超过$O(\sqrt N)$。
### Min-25 筛
要求：
1. $f(p)$是p的简单多项式（记为g）。
2. $f(p^c)$可以快速求值。
#### Part 1
对于所有整除分块内出现过的n，求出$g(n,i)$： n以内所有的质数以及最小质因子大于$p_i$的数g之和，即埃筛跑i轮剩下部分的g之和。
先将g拆成单项式，对于每一项分别处理。
初值：$g(n, 0) = \sum_{i=2}^n i^k
转移：在上一轮剩下来的数中减去最小质因子恰好为p_i的g之和。
g(n,i) = g(n,i-1)-p_i^k(g(\lfloor{n \over p_i}\rfloor,i-1)-\sum_{j=1}^{i-1}p_j^k)
我们规定比较小的质数也是合法的（虽然最小质因子小于p_i），所以需要枚举形如p_i p_j(j<i)的数避免减重。
实现：维护多项式的点积。从小到大枚举质数，从大到小枚举$\lfloor {n \over x} \rfloor$，滚动数组，到p平方后退出。
#### Part 2
所有f的和分为3个部分：1，质数和合数。前两个部分已经在Part 1里求出。
对于合数，枚举其最小质因子p及p的幂。剩下的部分最小质因子严格大于p，考虑递归求解。
$$
S(n,i)=\sum_{j \geq i}f(j)+\sum_{j \geq i}^{lim}\sum_{e \geq 1}(f(p_j^e)S(\lfloor{n \over p^e}\rfloor,j+1)+f(p_j^{e+1}))
$$
左式就是（合并后的）$g(n,lim)$减去一个质数的前缀和。lim表示根号n范围内质数个数。右式枚举p和e。
暴力搜索，不记忆化，复杂度是$O(n^{1-\epsilon})$。有意义的范围($10^{13}$)内可以看成$O({n^{3/4} \over \log n})$。
### 更多的应用
Min-25筛应用范围相当广。而所谓“简单多项式”其实是不需要的。
对于Part 1，我们的要求是：至少这个函数在素数处得非常简单。比如，它可以拆成几个完全积性的部分。我们还可以用别的可以求的函数组合得到这个函数。
对于Part 2，只要可以做形如$f(n p^{\alpha}) \leftarrow f(n)$的dp即可。我们也可以设两个函数相互推。
总之，可以使用Min-25筛不是一个非常强的条件，并且有着明显的迹象（$10^{10}$左右的数据范围，前缀统计等等）。
### 洲阁筛
第一部分，和Min-25筛第一部分本质相同。
第二部分，本质上就是将Min-25筛第二部分采取递推实现。
预先加入所有质数，即令$S(n, lim + 1) = g(n,lim)$。
之后从大往小枚举不超过根号n范围内的质数，加入以它为最小质因子的合数。
$$ S(n,i)=S(n,i+1)+\sum_{e \geq 1 \&p_i^{e+1}\leq n}(f(p_i^e)(S(\lfloor{n \over p_i^e}\rfloor,i+1)-\sum_{k=1}^{i}f(p_k))+f(p_i^{e+1})) $$
证出来是$O({n^{3/4} \over \log n})$的。
如果求单个S用Min-25筛更快。求块筛的话用这个方法。代码复杂度其实递推稍微短一些。
**这个东西被杜教筛吊着打，能不用就不用。**