首页 📚学习笔记

Dirichlet (狄利克雷)卷积

如果有两个数论函数$g(x),f(x)$,那么他们的狄利克雷卷积得到的$h(x)$为

$$ h(x)=\sum_{d|n}f(d)g(\frac{n}{d}) $$

简记为$h=f*g$,并且满足交换律结合律分配律

单位根

我们定义狄利克雷卷积的单位根为$\varepsilon$,所以有$f*\varepsilon=f$

常用卷积

$$ \begin{align} \varepsilon=\mu\ast1 &\iff \varepsilon(n)=\sum_{d|n}\mu(d)\\ d=1*1&\iff d(n)=\sum_{d|n}1\\ \sigma=id\ast1 &\iff \sigma(n)=\sum_{d|n}d\\ \varphi=\mu\ast id &\iff \varphi(n)=\sum_{d|n}d·\mu(\frac{n}{d})\\ \end{align} $$


莫比乌斯函数

$$ \mu(n)=\begin{cases}1\quad n=1\\0\quad n含有平方因子\\ (-1)^k \quad k为n本质不同的质因子个数\end{cases} $$

可知一个数$n$可以被分解为$\prod_{i}p_i^{k_i}$,也就是质数相乘,当有$k_i>1$时,即出现平方因子,此时$\mu(n)=0$

性质

$$ \sum_{d|n}\mu(d)=\begin{cases}1\quad n=1\\0\quad n\not=1\end{cases} $$


证明:
假设$n=\prod_{i}p_i^{k_i},n'=\prod_{i}p_i$

显然$\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)$因为平方因子没贡献的啊

这时就可以转换成枚举因数的质因子个数(假设质因子有$k$个)

$$ \begin{align} \sum_{d|n}\mu(d)&=\sum_{d|n'}\mu(d)\\ &=\sum_{i=0}^{k}\binom{k}{i}(-1)^i \end{align} $$

根据二项式定理可知

$$ \begin{align} \sum_{i=0}^{k}\binom{k}{i}(-1)^i&=\sum_{i=0}^{k}\binom{k}{i}(-1)^i·1^{(k-i)}\\ &=(1-1)^k \end{align} $$

所以只有当$k=0$也就是$n=1$的时候,式子的值才为$1$,所以$\mu*1=\varepsilon$

我们经常用的就是

$$ [\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d) $$


杂项证明

$$ \begin{align} \varphi*1=id \end{align} $$

因为$\varphi$是积性函数,所以我们单独提出只有一种质因子的证明即可(以下就为$p$)

$$ \begin{align} \varphi*1&=\sum_{d|n}\varphi(d)\\ &=\sum_{i=0}^{k}\varphi(p^i)\\ &=1+(p^1-p^0)+(p^2-p^1)+...+(p^k-p^{k-1})\\ &=p^k=n \end{align} $$

并且两边同时卷上$\mu$就是

$$ \begin{align} \varphi*1&=id\\ \varphi*(1*\mu)&=id*\mu\\ \varphi*\varepsilon&=id*\mu\\ \varphi&=id*\mu\\ \end{align} $$


莫比乌斯反演


两个数论函数$f(n),g(n)$

$$ \begin{align} f(n)=\sum_{d|n}g(d)\iff g(n)=\sum_{d|n}f(d)·\mu(\frac{n}{d})\\ f(n)=\sum_{n|d}g(d)\iff g(n)=\sum_{n|d}f(d)·\mu(\frac{d}{n})\\ \end{align} $$

一般都用第一个,而且用卷积十分好证

$$ \begin{align} f&=g*1\\ f*\mu&=g*1*\mu\\ g&=f*\mu \end{align} $$




文章评论

目录