狄利克雷前缀和与贝尔级数小结

vectorwyx · 2022-07-31 11:12:45 · 个人记录

（以下如无特殊说明提到 p 默认 p 为质数）

狄利克雷前缀和

给定数论函数 g，求 f 满足 f(i)=\sum_{j\mid i}g(j)。这是标准的狄利克雷前缀和，相信大家都会做。

给定数论函数 g，求 f 满足 f(i)=\sum_{j\mid i}g(j)\mu(\frac{i}{j})，第一次见可能不那么会做。这其实是容斥形式的高维差分，即给定高维前缀和数组 g 反推原数组 f。换句话说就是狄利克雷前缀和的逆过程，把做狄利克雷前缀和的过程里涉及到的所有操作取逆即可。

给定数论函数 g，求 f 满足 f(i)=\sum_{j\mid i}jg(\frac{i}{j})。小 trick，把 j 改写为 \frac{i}{\frac{i}{j}}，令 g(i)\to \frac{g(i)}{i}，f(i)=\sum_{j\mid i}g(j)，f(i)\times i 即为答案。

以上三个例子用狄利克雷卷积的角度看分别是在求 g*1,g*\mu,g*\operatorname{id}。 那如果给定任意一个数论函数 g 和积性函数 h，怎么快速求 g*h？注意到积性函数可以看做若干个只在 p^k 处有值的数论函数的卷积，形式化地讲，记 h_p(i)=\begin{cases}h(i)&i=p^k\\0&\operatorname{otherwise}\end{cases} ，则 h=\prod h_p（p 为质数），这里数论函数乘法即狄利克雷卷积。

狄利克雷卷积具有交换律和结合律，那么 g*h 等价于 g*h_{p_1}*h_{p_2}*\cdots，其中 p_i 为第 i 个质数。于是求 g*h 就可以先求 g*h_{p_1} 得到 g'，再求 g'*h_{p_2} 得到 g''，以此类推……于是问题就变为给定数论函数 g 和一个只在 p^k 处有值的数论函数 h_p，求 g*h_p。直接老老实实地按定义卷起来就好，具体地，先把 h_p(p) 拿出来，对于所有 p 的倍数 kp，把 g(k)\times h_p(p) 贡献到 g(kp)，再把 h_p(p^2) 拿出来，对于 p^2 的所有倍数 kp^2，把 g(k)\times h_p(p^2) 贡献到 g(kp^2)，以此类推……如果只关心 \le n 的取值，复杂度是 \sum_{i>0}\frac{n}{p^i}=O(\frac{n}{p})。但看上去需要拷贝数组啊？严格来讲确实需要，不过这里比较特殊，我们可以直接在原数组上进行操作。实现时类似背包问题的转移，为了防止贡献多次，需要倒着进行。写成代码大概长这样：

for(int i){
    int p=pme[i];//第 i 个质数 p 
    for(int j=n-n%p;j>0;j-=p){
        int x=j;
        while(x%p==0){
            x/=p;
            g[j]=g[j]+g[x]*h[j/x];
        }
    }
}

最终得到的 g 数组就是 g*h 的结果。

用这个视角回看刚开始提到的 g*1,g*\mu 与 g*\operatorname{id}。g*1 的通用写法大概是：

for(p is prime) 
    for(i=1 to n/p) g[i*p]+=g[i];

这实际上是把常函数 1 分解为了 h_p(i)=\begin{cases}1&i=p^k\\0&\operatorname{otherwise}\end{cases}，然后依次考虑每个质数 p，令 g(ip^k)=\sum_{j=0}^{k}g(ip^j)。把 i,ip,ip^2\cdots 单拎出来看做一条数轴，这其实就是在这条数轴上做前缀和。而上述代码是同时对所有这样的数轴都进行前缀和，理解起来非常自然。

同理可得另两个的处理方法。g*\mu：

for(p is prime) 
    for(i=n/p to 1) g[i*p]-=g[i];