9. 莫比乌斯函数与莫比乌斯反演
9.1 莫比乌斯函数
9.1.1 定义
设 \(\mu\) 为莫比乌斯函数，则有：
\[\mu(x)=\begin{cases}1\qquad (n=1)\\ 0\qquad (∃\ i\ (ki=x,k\in Z\rightarrow \sqrt{i}\in Z))\\ (-1)^{\sum_{i\in prime}[i\mid x]}\end{cases} \]直观地说，只要 \(x\) 的某个质因子出现的次数超过一次，则有 \(\mu(x)=0\)，否则，\(mu(x)\) 即为 \((-1)^{t}\)，其中 \(t\) 为 \(x\) 的质因数总数.
9.1.2 性质
\(No.9121\) \(\forall (i,j)=1\rightarrow\mu(i\times j)=\mu(i)\times \mu(j)\)
\[P.9121 \]若 \(\mu(A)=1\)，则有 \(\mu(A)\times \mu(B)=1\times \mu(B)=\mu(1\times B)\)，结果成立
若 \(\mu(A)=0\)，则有 \(\mu(A)\times\mu(B)=0\)，结果成立
否则设 \(A=\prod_{i\in prime}i,B=\prod_{j\in prime}j\ (\forall i\neq j)\)，则有 \(\mu(A)\times\mu(B)=\mu(A\times B)\)
\(No.9122\)
\[\sum_{d\mid n}\mu(d)=\begin{cases}1\qquad (n=1)\\0\qquad(n\neq 1)\end{cases} \]\[P.9122 \]\(n=0\) 时，原式等于 \(0\)
\(n=1\) 时，原式等于 \(\mu(1)=1\)
否则，设 \(n\) 的唯一分解式为 \(n=\prod_{1\le i\le k}p_{i}^{a_{i}}\)，由 \(\mu(n)\neq 0\) 知 \(\forall a_{i}=1\)
显然，\(\forall d\mid n\)，有 \(i\) 个质因子的数 \(d\) 有 \(C^{i}_{k}\) 种组合情况，每种组合的值为 \((-1)^{i}\)，即：
\[\sum_{d\mid n}\mu(d)=\sum_{0\le i\le k}\{C^{i}_{k}\times (-1)^{i}\} \]使用二项式定理转化：
\[\sum_{d\mid n}\mu(d)=(1+(-1))^{k}=0^{k} \]发现此时在定义域 \((k\neq 0)\) 内恒为 \(0\)，易知当 \(n\gt 1\) 时，\(k_{n}\ge 1\)，因此 \(\mu(n)=0\)，证毕.
9.2 莫比乌斯反演
9.2.1 不完全结论
设
\[f(a,b,k)=\begin{cases}1\qquad((a,b)=k)\\0\end{cases} \]对于
\[g(n,m,k)=\sum^{n}_{i=1}\sum^{m}_{j=1}f(i,j,k) \]考虑到
\[g(n,m,k)=\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=1}\sum^{\lfloor{\frac{m}{k}}\rfloor}_{j-1}f(i,j,1) \]根据 \(No.9122\) 得出推导式：
\[\sum_{d\mid (a,b)}\mu(d)=\begin{cases}1\qquad ((a,b)=1)\\0\qquad((a,b)\neq 1)\end{cases} \]代入有：
\[f(i,j,1)=\sum_{d\mid (i,j)}\mu(d) \]即：
\[g(n,m,k)=\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=1}\sum^{\lfloor{\frac{m}{k}}\rfloor}_{j-1}=\sum_{d\mid (i,j)}\mu(d) \]将原式等价转换，可以得到
\[g(n,m,k)=\sum_{d=1}\mu(d)\sum^{\lfloor{\frac{n}{k}}\rfloor}_{i=1}\sum^{\lfloor{\frac{m}{k}}\rfloor}_{j-1}h(i,j) \]其中
\[h(i,j)=\begin{cases}1\qquad(d\mid i,d\mid j)\\0\end{cases} \]（可以发现，在这里仅仅是将判断条件与枚举条件互相变换了，而答案是不变的）
在区间 \([1,\lfloor{\frac{n}{k}}\rfloor]\) 中，满足条件 \(d\mid i\) 的 \(i\) 有 \(\lfloor{\frac{n}{kd}}\rfloor\) 个，因此原式可化为
\[g(n,m,k)=\sum_{d=1}\mu(d)\times\lfloor{\frac{n}{kd}}\rfloor\times\lfloor{\frac{m}{kd}}\rfloor \]可以证明，当 \(d\gt \min(\lfloor{\frac{n}{k}}\rfloor,\lfloor{\frac{m}{k}}\rfloor)\) 时不存在解.
9.2.2 完全结论
博主去学卷积了，学完回来更
标签：lfloor,frac,乌斯,sum,rfloor,times,mu,反演,莫比 From： https://www.cnblogs.com/HaneDaCafe/p/18315650