狄利克雷卷积

· · 个人记录

常用函数符号

\bullet\varepsilon \left(n\right)=\left\{\begin{matrix}1\cdots\left[n=1\right]\\ 0\cdots\left[n\ne1\right]\end{matrix}\right. \bullet Id_{k}\left(n\right)=n^{k} \bullet \sigma_{k}\left(n\right)=\sum\limits_{d\mid n}d^{k}

定义n=\prod\limits_{i=1}^{k}p_{i}^{c_{i}},\forall i\in\left[1,k\right],p_{i}为质数

\bullet\varphi\left(n\right)=n\prod\limits_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)

积性函数

若当\left(a,b\right)=1时f\left(ab\right)=f\left(a\right)f\left(b\right)且f\left(1\right)=1,则称f\left(x\right)为积性函数

### 狄利克雷卷积 定义$h\left(n\right)=f\left(n\right)\times g\left(n\right)=\sum\limits_{d\mid n}f\left(n\right)g\left(\frac{n}{d}\right)

函数关系

Id_{k}\times 1=\sigma_{k} \varphi\times 1=Id

狄利克雷卷积的性质

1.若f,g为积性函数,则f\times g也是积性函数
2.f\times g=g \times f
3.f\times \left(g\times h\right)=\left(f\times g\right)\times h
4.\left(f\times\left(g+h\right)\right)=f\times g+f\times h

狄利克雷逆元

若f\times g=\varepsilon，则称g是f的狄利克雷逆元,记为f^{-1}

莫比乌斯反演

莫比乌斯函数

记n=\prod\limits_{i=1}^{k}p_{i}^{c_{i]}}
定义\mu\left(n\right)=\left\{\begin{matrix}1\cdots\left[n=1\right]\\ 0\cdots \left[\exists i\in\left[1,k\right],c_{i}>0\right]\\ \left(-1\right)^{k}\cdots\left[\forall i\in\left[1,k\right],c_{i}=1\right]\end{matrix}\right.

莫比乌斯函数的性质

1.\mu是积性函数
2.\sum\limits_{d\mid n}\mu\left(d\right)=\left\{\begin{matrix}1\cdots\left[n=1\right]\\ 0\cdots\left[n\ne1\right]\end{matrix}\right.

反演结论

\left[\left(i,j\right)=1\right]=\sum\limits_{d\mid \left(i,j\right)}\mu\left(d\right)

莫比乌斯变化

设f,g是两个数论函数

\bullet f\left(n\right)=\sum\limits_{d\mid n}g\left(d\right)\Rightarrow g\left(n\right)=\sum\limits_{d\mid n}\mu\left(d\right)f\left(\frac{n}{d}\right) \bullet f\left(n\right)=\sum\limits_{n\mid d}g\left(d\right)\Rightarrow g\left(n\right)=\sum\limits_{n\mid d}\mu\left(\frac{d}{n}\right)f\left(d\right)