您也可以阅读体验更好、叙述更严谨的论文。
积性函数
数论函数是指定义域在正整数、而值域在复数域上的一类函数，即\(f:\mathbb{Z}^{+}\rightarrow\mathbb{C}\)。
下文中的数论函数值域都在整数上。积性函数是一种特殊的数论函数，他们满足对于任意互质的一对数\(p,q\)，有\(f(p)\cdot f(q)=f(pq)\)，即他们的函数值乘起来等于他们乘起来的函数值。特别地，如果对于任意不互质两数上面的条件也成立，则称这个函数为完全积性函数。
我们对两数$p,q$互质的定义为\(\gcd(p,q)=1\)，所以我们称\(1\)和其他所有数都互质。于是我们可以知道对于一个积性函数\(f\)，\(f(1)=1\)（除非它的所有函数值都是零）。
常用的积性函数
\(\mu(n)\)，莫比乌斯函数。它的定义比较复杂，下面再写。
\(\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]\)，欧拉函数，即在比不大于这个数的与他互质的数的个数。
\(d(n)=\sum_{i|n}1=\sum_{i=1}^{n}[i|n]\)，约数个数。
\(\sigma(n)=\sum_{i|n}i=\sum_{i=1}^{n}[i|n]\cdot i\)，约数和，即这个数的各个约数之和。
常用的完全积性函数
\(\epsilon(n)=[n=1]\)，元函数，只在\(n\)为\(1\)时为\(1\)，其他时候都为\(0\)。
\(I(n)=1\)，恒等函数，他的值永远等于\(1\)。
\(id(n)=n\)，单位函数。
莫比乌斯函数
莫比乌斯函数的定义严格地来写是这样的
我们设\(n\)分解后有\(k\)个质因数，他们是这样的\[n={p_1}^{s_1}\times {p_2}^{s_2}\times {p_3}^{s_3}\times\cdots\times {p_k}^{s_k}\]那么对应的莫比乌斯函数值就可以写成\[
\mu(n)=
\begin{cases}
0&(存在一个 s_i>1)\\
1&(k为奇数)\\
-1&(k为偶数)
\end{cases}
\]写成这样就是一个很直白的容斥系数了，所以我们就有\[
\sum_{d|n}\mu(d)=[n=1]
\]怎么解释呢？如果\(n\)不是\(1\)，那么它的因数就两两配对，一对因数的\(\mu\)要么都是\(0\)要么一个是\(1\)一个是\(-1\)，求和就都是\(0\)了。
有了这个，再配合交换求和号的知识、整除分块和线性筛，顺便再充分理解一下约数和原数的大小关系之类的，你就可以解决很多没有毒瘤数据的数论裸题了。
线性筛求积性函数值
实际上，积性函数可以在线性筛的过程中顺便求出来，只要在找到质数的时候设置一下初值，然后筛去合数的过程中如果两个因数互质则直接乘起来，不互质则……
对于\(\mu\)，这时\(p\times i\)出现了次数为\(2\)的项，我们直接赋成0就可以了；对于\(\varphi\)，这个稍稍有点复杂，可以证明当\(p\)为质数且\(\gcd(p,i)\neq 1\)时有\(\varphi(p\times i)=\varphi(i)\times p\)。于是我们就可以写出下面的代码：
狄利克雷卷积
狄利克雷卷积是一种将两个积性函数“卷起来”的一种操作，记作\(h=f*g\)，它的结果仍然是一个积性函数：\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})=\sum_{d|n}f(\frac{n}{d})g(d)\]这相当于枚举n的每一个约数，把相应的一对因数分别带进去求值乘起来，然后再都加起来。
狄利克雷卷积像一个普通的乘法一样，具有：
交换律：\(f*g=g*f\)；
结合律：\((f*g)*h=f*(g*h)\)；
分配律：\((f+h)*g=f*g+h*g\)。
对于狄利克雷卷积，我们有元函数卷上任意一个函数，结果还是那个函数，元函数扮演了单位元的角色。\[f*\epsilon=f\]
重写一些性质
我们可以把\(\mu\)的性质重写成卷积的形式：\[\mu*I=\epsilon\]\(\varphi\)也可以这样重写：\[\sum_{d|n}\varphi(d)=n\Longleftrightarrow\varphi*I=id\]
实际上，\(\mu\)和\(\varphi\)有着以下的奇妙关系：\[\frac{\varphi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}\]证明的话，只要把\(\varphi*I=id\)两边各卷上一个\(\mu\)然后把\(I*\mu\)结合成\(\epsilon\)就好了。
莫比乌斯反演
莫比乌斯反演定理：若\(F\)和\(f\)是两个数论函数，并且他们满足\[F(n)=\sum_{d|n}f(n)\]则有\[f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})F(d)\]证明类似，先写成\(F=f*I\)然后再两边卷上一个\(\mu\)即可得到\(F*\mu=f\)。