狄利克雷卷积学习笔记

蒟蒻尚在学习，请各位dalao不要相信本文的任何一个字，包括标点符号。

什么是狄利克雷卷积

狄利克雷卷积定义式如下：

$f\cdot g(n)=\sum_{dn}f(d)\cdot g(\frac{n}{d})$

也可以写作：

$f\cdot g(n)=\sum_{i\cdot j=n}f(i)\cdot g(j)$

怎么算狄利克雷卷积

单独计算$f*g(n)$

显然我们可以根据定义式暴力计算，枚举$i$即可，复杂度$O(\sqrt{n})$ 这里就不上代码了，跟暴力枚举质数长得基本上一模一样。

计算$f*g$

如果再像暴力计算那样，复杂度将达到恐怖的$O(n\sqrt{n})$。

但是我们可以从质数筛（埃筛）的想法入手，我们可以直接枚举一个$i$，再为它的倍数上的值加上对应的贡献就好。时间复杂度$O(nlogn)$。

代码大概长这样w

1
2
3
4
5
6
7

void Dirichlet(int f[],int g[],int ans[],int n)
{
    memset(ans,0,sizeof ans);
    for(int i=1;i<=n;i++)
        for(int j=1;i*j<=n;j++)
            ans[i*j]+=f[i]*g[j];
}

怎么样，是不是比FFT容易一千万倍？

狄利克雷卷积有什么性质

满足： 1. 交换律 2. 结合律 3. 分配率