补充一下莫比乌斯反演的前置知识
狄利克雷乘积(Dirichlet product)亦称狄利克雷卷积、卷积，是数论函数的重要运算之一。设f(n)、g(n)是两个数论函数，它们的Dirichlet(狄利克雷)乘积也是一个数论函数，简记为h(n)=f(n)*g(n)。
前置知识：积性函数
规定几种函数：
\[单位函数：\epsilon(n) = \left\{ \begin{aligned} 1 \qquad n = 1 \\ 0 \qquad n > 1 \end{aligned} \right. \\ 幂函数：Id_{k}(n) = n^{k} \\ 常数函数：1(n) = 1 \\ 整除函数：\sigma_{k}(n) = \sum_{d \mid n} d^{k}\\ 欧拉函数：\phi(n) \]对于函数f和g，狄利克雷卷积的运算过程为：
\[(f * g)(n) = \sum_{d \mid n} f(d)g(\frac{n}{d}) \]性质：
1.若f，g为积性函数，则\(f*g\)也为积性函数。
2.狄利克雷卷积满足交换律，\(f * g = g * f\)
3.狄利克雷卷积满足结合律，\(f*(g * h) = (f * g) * h\)
4.狄利克雷卷积满足分配律，\(f * (g + h) = f * g + f * h\)
5.\(Id_{k} * 1 = \sigma_{k}\)
证明：
\[(Id_{k} * 1)(n) = \sum_{d \mid n}Id_{k}(d)\cdot 1(\frac{n}{d}) = \sum_{d \mid n} d^{k} = \sigma_{k}(n) \]6.\((\phi * 1) = Id\)
证明：
设为\(p\)质数，\(m > 0\)
\[(\phi * 1)(p^{m}) = \sum_{d \mid p^{m}}\phi(d) = \sum_{i = 0}^{m} \phi(p^{i}) = p^{0} + \sum_{i = 1}^{m}(p^{i} - p^{i - 1}) = p^{m} \]因为n可以表示为\(n = p_1^{m_1} \cdot p_2^{m_2} \cdot ... \cdot p_r^{m_r}\),由积性函数的性质可得\((\phi * 1)(n) = n = Id(n)\)
证毕
7.\((\epsilon * f)(n) = \sum_{d \mid n} f(d)\epsilon(\frac{n}{d}) = f(n)\)
狄利克雷逆元
在狄利克雷卷积中，单位元是\(\epsilon\)，定义狄利克雷逆元如下：
\[f * f^{-1} = \epsilon \]则将\(f^{-1}\)称为\(f\)的逆元
几个性质：
1.\(f^{-1}(1) = \frac{1}{f(1)}\)
2.对于\(n > 1\)有：
\[f^{-1}(n) = -\frac{1}{f(1)} \cdot \sum_{d \mid n , d > 1} f(d)f^{-1}(\frac{n}{d}) \]证明：
\(n = 1\)时：
\[1 = \epsilon (1) = (f * f^{-1})(1) = \sum_{d \mid 1}f(d)f^{-1}(\frac{1}{d}) = f(1)f^{-1}(1)\\ 可得：f^{-1}(1) = \frac{1}{f(1)} \]\(n \neq1\)时：
\[(f * f^{-1})(n) = \sum_{d \mid n}f(d)f^{-1}(\frac{n}{d}) = f(1)f^{-1}(n) + \sum_{d \mid n, d > 1}f(d)f^{-1}(\frac{n}{d})\\ = f(1) \cdot (-\frac{1}{f(1)})\sum_{d \mid n, d > 1}f(d)f^{-1}(\frac{n}{d}) + \sum_{d \mid n, d > 1}f(d)f^{-1}(\frac{n}{d}) = 0 = \epsilon(n) \]证毕
3.\(\mu^{-1}(n) = 1\)
证明：
\[因为：\epsilon(n) = (\mu * \mu^{-1})(n) = \sum_{d \mid n}\mu(d)\mu^{-1}(\frac{n}{d}) \\ 且；\epsilon(n) = \sum_{d \mid n}\mu(d)\\ 所以：\mu^{-1}(n) = 1(n) = 1 $$\ 暂时写这么多\] 标签：frac,狄利克,卷积,epsilon,sum,mid From： https://www.cnblogs.com/mcggvc/p/16900584.html