莫比乌斯反演常用结论

内容主要来自oi-wiki
##前置知识 \[ \forall a,b,c\in\mathjaxbb{Z},\left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor \]
数论分块的过程大概如下：考虑含有 \(\left\lfloor\frac{n}{i}\right\rfloor\) 的求和式子（ \(n\) 为常数）

对于任意一个 \(i(i\leq n)\) ，我们需要找到一个最大的 \(j(i\leq j\leq n)\) ，使得 \(\left\lfloor\frac{n}{i}\right\rfloor = \left\lfloor\frac{n}{j}\right\rfloor\) .

此时 \(j=\left\lfloor\frac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor\) .

显然 \(j\leq n\) ，考虑证明 \(j\geq i\) ：

\[ \begin{aligned} &\left\lfloor\frac{n}{i}\right\rfloor \leq \frac{n}{i}\\ \implies &\left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor \geq \left\lfloor\frac{n}{ \frac{n}{i} }\right\rfloor = \left\lfloor i \right\rfloor=i \\ \implies &i\leq \left\lfloor\frac{n}{ \left\lfloor\frac{n}{i}\right\rfloor }\right\rfloor=j\\ &&\square \end{aligned} \]

不妨设 \(k=\left\lfloor\frac{n}{i}\right\rfloor\) ，考虑证明当 \(\left\lfloor\frac{n}{j}\right\rfloor=k\) 时， \(j\) 的最大值为 \(\left\lfloor\frac{n}{k}\right\rfloor\) ：

\[ \left\lfloor\frac{n}{j}\right\rfloor=k \iff k\leq\frac{n}{j}<k+1 \iff \frac{1}{k+1}<\frac{j}{n}\leq\frac{1}{k} \iff \frac{n}{k+1}<j\leq\frac{n}{k} \]

又因为 \(j\) 为整数 所以 \(j_{max}=\left\lfloor\frac{n}{k}\right\rfloor\)

利用上述结论，我们每次以 \([i,j]\) 为一块，分块求和即可

积性函数

定义

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y \in \mathjaxbb{N}_{+},\gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\) ，则 \(f(n)\) 为积性函数。

若函数 \(f(n)\) 满足 \(f(1)=1\) 且 \(\forall x,y \in \mathjaxbb{N}_{+}\) 都有 \(f(xy)=f(x)f(y)\) ，则 \(f(n)\) 为完全积性函数。

性质

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

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

设 \(x=\prod p-i^{k-i}\)

若 \(F(x)\) 为积性函数，则有 \(F(x)=\prod F(p-i^{k-i})\) 。

若 \(F(x)\) 为完全积性函数，则有 \(F(X)=\prod F(p-i)^{k-i}\) 。 ###常见数论函数 - 单位函数： \(\epsilon(n)=[n=1]\) （完全积性） - 恒等函数： \(\operatorname{id}-k(n)=n^k\) \(\operatorname{id}_{1}(n)\) 通常简记作 \(\operatorname{id}(n)\) 。（完全积性） - 常数函数： \(1(n)=1\) （完全积性） - 除数函数： \(\sigma_{k}(n)=\sum_{d\mid n}d^{k}\) \(\sigma_{0}(n)\) 通常简记作 \(\operatorname{d}(n)\) 或 \(\tau(n)\) ， \(\sigma_{1}(n)\) 通常简记作 \(\sigma(n)\) 。 - 欧拉函数： \(\varphi(n)=\sum_{i=1}^n [\gcd(i,n)=1]\) - 莫比乌斯函数： \(\mu(n) = \begin{cases}1 & n=1 \\ 0 & \exists d>1:d^{2} \mid n \\ (-1)^{\omega(n)} & otherwise\end{cases}\) ，其中 \(\omega(n)\) 表示 \(n\) 的本质不同质因子个数，它也是一个积性函数。

Dirichlet 卷积

定义

定义两个数论函数 \(f,g\) 的 Dirichlet 卷积为

\[ (f\ast g)(n)=\sum_{d\mid n}f(d)g(\frac{n}{d}) \]

性质

Dirichlet 卷积满足以下运算规律：

• 交换律 \((f * g=g * f)\) ；
• 结合律 \((f * g) * h=f * (g * h)\) ；
• 分配律 \(f * (g+h)=f * g+f * h\) ；
• \(f*\varepsilon=f\) ，其中 \(\varepsilon\) 为 Dirichlet 卷积的单位元（任何函数卷 \(\varepsilon\) 都为其本身）

例子

\[ \begin{aligned} \varepsilon=\mu \ast 1&\iff\varepsilon(n)=\sum_{d\mid n}\mu(d)\\ d=1 \ast 1&\iff d(n)=\sum_{d\mid n}1\\ \sigma=\operatorname{id} \ast 1&\iff\sigma(n)=\sum_{d\mid n}d\\ \varphi=\mu \ast \operatorname{id}&\iff\varphi(n)=\sum_{d\mid n}d\cdot\mu(\frac{n}{d}) \end{aligned} \]

莫比乌斯函数

莫比乌斯函数不但是积性函数，还有如下性质：

\[ \sum_{d\mid n}\mu(d)= \begin{cases} 1&n=1\\ 0&n\neq 1\\ \end{cases} \]

即 \(\sum_{d\mid n}\mu(d)=\varepsilon(n)\) ， \(\mu * 1 =\varepsilon\)

莫比乌斯反演

公式

设 \(f(n),g(n)\) 为两个数论函数。

如果有 \(f(n)=\sum_{d\mid n}g(d)\) ，那么有 \(g(n)=\sum_{d\mid n}\mu(d)f(\frac{n}{d})\) 。

如果有 \(f(n)=\sum_{n|d}g(d)\) ，那么有 \(g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)\) 。

证明

方法一：对原式做数论变换。

\[ \sum_{d\mid n}\mu(d)f(\frac{n}{d})=\sum_{d\mid n}\mu(d)\sum_{k\mid \frac{n}{d}}g(k)=\sum_{k\mid n}g(k)\sum_{d\mid \frac{n}{k}}\mu(d)=g(n) \]

用 \(\displaystyle\sum_{d\mid n}g(d)\) 来替换 \(f(\dfrac{n}{d})\) ，再变换求和顺序。最后一步变换的依据： \(\displaystyle\sum_{d\mid n}\mu(d)=[n=1]\) ，因此在 \(\dfrac{n}{k}=1\) 时第二个和式的值才为 \(1\) 。此时 \(n=k\) ，故原式等价于 \(\displaystyle\sum_{k\mid n}[n=k]\cdot g(k)=g(n)\)

方法二：运用卷积。

原问题为：已知 \(f=g\ast1\) ，证明 \(g=f\ast\mu\)

易知如下转化： \(f\ast\mu=g*1*\mu\implies f\ast\mu=g\) （其中 \(1\ast\mu=\varepsilon\) ）。