莫比乌斯反演入门

大部分从oiwiki上看到的，有误欢迎大佬斧正

积性函数

定义

若 \(f(x)f(y)=f(xy)\)且\((x,y)=1\) ，则 \(f(x)\)为积性函数。

性质

若\(f(x)\)和\(g(x)\)均为积性函数，则以下函数也为积性函数：

\[\begin{align}&h(x)=f^p(x)\&h(x)=f(x^p)\&h(x)=f(x)g(x)\&h(x)=\sum_{d\mid x}f(d)g(x/d) \end{align}\]

常见积性函数

1. 约数函数 \(\sigma_k(n)=\sum_{d\mid n}d^k\) 表示n的约数的k次幂之和
2. 约数和函数 \(\sigma(n)=\sum_{d\mid n}d\) 表示n的约数和 (\(3.1,k=1\))
3. 约数个数函数 \(\tau(n)=\sum_{d\mid n}1\) 表示n的约数个数 通常也写作\(d(n)\)
4. 欧拉函数 \(\phi(n)=\sum_{i=1}^{n-1}(i,n)=1\) 表示\([1,n-1]中与n互素的数的个数\)
5. 莫比乌斯函数 \[\mu(n)=\begin{cases}1 & n=1\\0 & \exists d: d^2\mid n\\(-1)^{\omega(n)} & otherwise\end{cases}\] \(\omega(n)\mbox{表示n的不同素因子个数}\) 与常数函数在迪利克雷卷积中互为逆元
6. 单位函数 \(\epsilon(n)=[n=1]\) 迪利克雷卷积中的单位元
7. 幂函数 \(id_k(n)=n^k\)
8. 恒等函数 \(id(n)=n\)
9. 常数函数 \(1(n)=1\)
   最后三个为完全积性函数

迪利克雷卷积

定义

定义两个数论函数\(f,g\)的迪利克雷卷积为
\[(f*g)(n)=\sum_{d\mid n}f(d)g(n/d)\]

性质

1. 交换律
2. 结合律

常见积性函数卷积

1. \(\epsilon=\mu*1 \Leftrightarrow \epsilon(n)=\sum_{d\mid n}\mu(d)\) 单位函数等于莫比乌斯函数和常函数的卷积
2. \(d=1*1 \Leftrightarrow d(n)=\sum_{d\mid n}1*1\) 约数个数函数等于常函数与常函数作卷积
3. \(\sigma=d*1 \Leftrightarrow \sigma=\sum_{d\mid n}d\) 约数和函数等于约数个数函数和常函数作卷积
4. \(\phi=id*\mu \Leftrightarrow \phi(n)=\sum_{d\mid n}d\mu(n/d) \Leftrightarrow \frac{\phi(n)}{n}=\sum_{d\mid n}\frac{\mu(d)}{d}\)
5. \(id=\phi*1\),可由前面式子推出，将4式代入，右边=\(\mu*1*id\),莫比乌斯函数和常数函数互为逆元，卷积为单位函数则最后结果为恒等函数id

单位函数证明

\(\epsilon(n)\sum_{d\mid n}\mu(d)\),根据唯一分解定理\(n=\prod_{i=1}^q p_i^{r_i}\)
已知当n有平方因子时，\(\mu(n)=0\)，此时对答案无贡献，我们不妨将\(n\mbox{转换为}n'=\prod_{i=1}^q p_i\)
那么约数就是\(\{p_1,p_2,...p_q\}\)的组合，\[\epsilon(n)=\sum_{d\mid n}\mu(d)=\sum_{d\mid n'}\mu(d)=\sum_{i=0}^qC(q,i)(-1)^i=0,n\gt 1\]
最后一步由二项式定理的来，\((1+(-1))^k=0\)

补充结论

\([gcd(i,j)=1 \Leftrightarrow \sum_{d\mid gcd(i,j)}\mu(d)\)，十分有用！！！

莫比乌斯反演

公式

\(f(n),g(n)\)是两个数论函数,如果有
\[f(n)=\sum_{d\mid n}g(d), ①\]
对于\(g(n)\)有反演公式
\[g(n)=\sum_{d\mid n}\mu(d)f(n/d), ②\]

证明

将

莫比乌斯反演入门

原文：https://www.cnblogs.com/mooleetzi/p/11370386.html