狄利克雷卷积 初级知识详解

在说狄利克雷卷积之前，最主要的是学会整除分块，不仅仅是结论，更重要的是推导过程（详见这里：传送门）

整除分块是第一步，第二步是乱七八糟的数论函数；

首先介绍一下数论函数：定义域为正整数，值域为复数的一个子集的函数

对于数论函数(本文以下部分若未特殊说明省略"数论函数")$f(x)$,若对于任意互质的正整数x,y,$f(xy)=f(x)f(y)$,则该数论函数是积性函数；

如果没有互质条件的限制，那么就称这个积性函数是完全积性函数；

常见的数论函数有如下几种：

1.单位函数：$ϵ(n)=\left\{\begin{matrix}1, & n=1 \\ 0, & n\neq 1 \end{matrix}\right.$

即：$ϵ(n)=[n=1]$;

它是完全积性函数；

2.标号函数：$Id_{k}(n)=n^{k}$;

特殊的，我们规定$Id(n)=Id_{1}(n)=n$, $Id_{0}$记作1；

　它也是完全积性函数；

3.除数函数：$σ_{k}(n)=\sum _{d\mid n}d^{k}$

　特殊的，我们规定$σ_{1}(n)$表示n的约数个数和，$σ_{0}(n)$表示n的约数个数；

　它是积性函数；

4.欧拉函数:这个相必大家都很熟悉，这里就不多说了；

5.莫比乌斯函数：$μ(n)=\left\{\begin{matrix}1,&n=1 \\ (-1)^{k},&n=p_{1}p_{2}...p_{k}\\0,&otherwise\end{matrix}\right.$

　它是一个积性函数；

好了，想必第一次看到这里的人一定还没记住上面那些乱七八糟的数论函数，但没关系，函数的定义都已经一一列举了出来，记不住的一边看下面一边看上面就好了；

接下来步入正题：狄利克雷卷积；

啥是这鬼东西？

对于数论函数$f(x),g(x),h(x)$,如果$h(x)=\sum _{d\mid n}f(d)g(\frac{n}{d})$,则称h是f和g的狄利克雷卷积，记作$h(x)=f(x)\ast g(x)$,简称f卷g；

1.交换律$f∗g=g∗f$

2.结合律$f*(g*h)=(f*g)*h$

3.分配律$f*(g+h)=f*g+f*h$

4.有单位元$ϵ\ast f=f\ast ϵ=f$

下面是常用的狄利克雷卷积公式：

1.$\varphi \ast 1=Id$

证明：

$\varphi \ast 1\Leftrightarrow \sum_{d\mid n}\varphi (d)=Id(n)$

设$f(d)=\sum_{1}^{n}[gcd(i,n)=d]$,则：$f(d)=\sum_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]=\varphi (\frac{n}{d})$

因为f(d)的定义是1~n中和n的最大公约数为d的个数；

所以：$\sum _{d\mid n}f(d)=n$;

因为：$\sum _{d\mid n}f(d)=n= \sum _{d\mid n}\varphi (\frac{n}{d})= \sum _{d\mid n}\varphi (d)=n$

所以得证;

2.$μ\ast 1=ϵ$

证明：

$μ\ast 1=ϵ\Leftrightarrow \sum_{d\mid n} μ(d)=ϵ(n)$

$n=1$时，式子显然成立；

现在要证明的就是:当$n>1$的时候，$\sum_{d\mid n} μ(d)=0$

根据莫比乌斯函数的定义和组合数的知识：

$\sum_{d\mid n} μ(d)=\sum_{i=0}^{k}(-1)^{i}C(k,i)$ 意义时k的不同的质因子中选取i个使其各取1个；

根据二项式定理：$(a+b)^{n}=\sum_{i=0}^{k}C(k,i)a^{k-i}b^{i}$

$\sum_{i=0}^{k}(-1)^{i}C(k,i)=(1-1)^{k}=0$

得证；

还有一些不是那么常用的，可以自己试着证一证；(太懒了不想打LaTex了)

3.$μ\ast Id=\varphi $

4.$Id \ast 1=σ_{1}$

5.$1 \ast 1=σ_{0}$

下面放上一道经久不衰的莫比乌斯反演狄利克雷卷积例题

题目大意：求：$\sum_{i=1}^{n}\sum_{j-1}^{m}[gcd(i,j)=k]$

$=\sum_{i=1}^{\frac{n}{k}}\sum_{j-1}^{\frac{m}{k}}[gcd(i,j)=1]$

$=\sum_{i=1}^{\frac{n}{k}}\sum_{j-1}^{\frac{m}{k}}ϵ(gcd(i,j))$

由狄利克雷卷积可知：$μ\ast 1=ϵ$(忘了的看上面)

$=\sum_{i=1}^{\frac{n}{k}}\sum_{j-1}^{\frac{m}{k}}\sum_{d\mid gcd(i,j)}μ(d)$

这时候发现式子好像推不动的样子了，所以改变枚举的东西:

$=\sum_{d=1}^{\frac{min(n,m)}{k}}μ(d)\sum_{d\mid i\bigcap i\leqslant \frac{n}{k}}^{} \sum_{d\mid j \bigcap j\leqslant \frac{m}{k}}^{}1$

$=\sum_{d=1}^{\frac{min(n,m)}{k}}μ(d)\frac{n}{k}\frac{m}{k}$

这时候式子就变得非常非常可爱了；

我们可以用欧拉筛来快速筛出1~n的莫比乌斯函数的前缀和；(不会的可以一边看代码，一边看莫比乌斯函数的定义，通过质数p来枚举p的倍数求得莫比乌斯函数)

而对于式子后面的部分，就用到了文章开头提到的东西:整除分块；

这样我们可以在$\sqrt n$的复杂度下求得这个式子的值了；

总复杂度时($m\sqrt n$);