概念引入

数论函数

　　　　指定义域为正整数的函数
　　　　定义其加法为逐项相加，即$(f + g)(n) = f(n) + g(n)$
　　　　定义其数乘为逐项相乘，即$(xf)(n) = x × f(n)$

单位元

　　　　单位元是集合中一种特别的元素，当单位元与其它元素相结合时，不会改变其它元素的值

逆元

　　　　逆元是指可以取消另一给定元素运算的元素，即将其变回单位元

符号表示

　　　　$[A]$表示条件$A$是否为真
　　　　此处的符号”$*$”表示狄利克雷卷积

狄利克雷卷积

　　令$t(n) = f(n) * g(n)$，则 　　

$$
t(n) = \sum\limits_{i | n} f(i)g(\frac{n}{i})
$$

　　那么狄利克雷卷积显然有下面几个性质：

满足乘法交换律、结合律、分配律

  • 对于单位元$\epsilon(n) = [n = 1]$，满足$\epsilon(n)*f(n) = f(n)$
    　　　　- 对于每一个$f(1) \ne 1$的数论函数$f(n)$，皆存在其逆元$f^{- 1}(n)$，满足$f(n) * f^{- 1}(n) = \epsilon(n)$，那么对于这个结论，可以令$f^{- 1}(n) = \frac{1}{f(1)}\left(\epsilon(n) - \sum\limits_{i | n, i \ne 1} f(i)f^{- 1}(\frac{n}{i})\right)$，再代回原式，满足条件

狄利克雷卷积与积性函数

积性函数

　　　　积性函数满足当$(n, m) = 1$，有$f(nm) = f(n)f(m)$

相关性质

  • 若$(n, m) = 1, d | nm$，则必定存在$a | n, b | m$且满足$ab = d$，证明显然

  • 若$(n, m) = 1, a | n, b | m$，则有$(a, b) = 1$，证明显然

​ 这样的话，就有性质：两个积性函数的狄利克雷卷积仍是积性函数，证明：
　　若$(n, m) = 1$，则有
$$
\begin{aligned}
t(nm) &= \sum\limits_{i | nm} f(i)g(\frac{nm}{i}) \\
&= \sum\limits_{a | n, b | m} f(ab)g(\frac{nm}{ab}) \\
&= \sum\limits_{a | n, b | m} f(a)f(b)g(\frac{n}{a})g(\frac{m}{b}) \\
&= t(n) * t(m)
\end{aligned}
$$

　　另外一个性质，就是两个积性函数的逆元仍是积性函数，是用数学归纳法证明：
　　　　令$(n, m) = 1$，当$nm = 1$时，结论显然成立
　　　　当$nm > 1$且$n_1m_1 < nm$时$n_1m_1$结论成立，再假设$nm$时结论成立，则有（注意，积性函数中一定满足$f(1) = 1$）
$$
\begin{aligned} f^{- 1}(nm) &= - \sum\limits_{i | nm, i \ne 1} f(i)f^{- 1}(\frac{nm}{i}) \\ &= - \sum\limits_{a | n, b | m, ab \ne 1} f(a)f(b)f^{- 1}(\frac{n}{a})f^{- 1}(\frac{m}{b}) \\ &= f(1)f(1)f^{- 1}(n)f^{- 1}(m) - \sum\limits_{a | n, b | m, ab \ne 1} f(a)f(b)f^{- 1}(\frac{n}{a})f^{- 1}(\frac{m}{b}) \\ &= f^{- 1}(n)f^{- 1}(m) - \epsilon(n)\epsilon(m) \\ &= f^{- 1}(n)f^{- 1}(m) \end{aligned}
$$
　　注：积性函数$f(1) = 1$

狄利克雷卷积与莫比乌斯反演

　　令$\mu$表示$1$在狄利克雷卷积意义下的逆元，令$g = f * 1$，则有$f = f * 1 * \mu = g * \mu$，再令$g(n) = \sum\limits_{d | n} f(d)$，则有

$$
f(n) = g(n) * \mu(n) = \sum\limits_{d | n} g(d)\mu(\frac{n}{d})
$$
　　这就是莫比乌斯反演的式子了
　　那么对于函数$\mu(n)$，由于$1$是积性函数，则$\mu$也是积性函数，又易知（代回原式就好了）
$$
\mu(p^k) = \left\{\begin{aligned} 1 k = 0 \\ - 1 k = 1 \\ 0 k > 1 \end{aligned}\right.
$$
　　那么由积性函数，可得
　　- 若$n = p_1p_2…p_k$且$p_1 \ne p_2 \ne … \ne p_k$，则有

$$
\mu(n) = (- 1)^k
$$

　　- 若$p_k^r | n (r > 1)$，则有

$$
\mu(n) = 0
$$

　　那么积性筛即可

另附

　　莫比乌斯反演的另一种形式，有

$$
g(n) = \sum\limits_{n | d}f(d)
$$
　　则有

$$
f(n) = \sum\limits_{n | d} \mu(\frac{d}{n})g(d)
$$