Part 1 前置芝士

1.1 数论函数

加性函数与积性函数均属于数论函数。 tip：$\gcd(p,q)=1$ 指 $p,q$ 互质。

1.2 莫比乌斯函数

$$\begin{array}{c} \mu(p^k)=\begin{cases}1&k=0\\-1&k=1\\0&k>1\end{cases} \\ \therefore \mu(n)=\begin{cases}1&n=1\\(-1)^k&\omega(n)=\Omega(n)=k \\0&\text{otherwise}\end{cases} \end{array}$$

tip： $\omega(n)=\Omega(n)=k$ 表示满足 $n=p_1p_{2}\dots p_k$ 且 $p_i$ 为 $n$ 的互异质因子。

$\text{otherwise}$ 指不满足上述条件。而上述条件中的 $p_{i}|n，\gcd(p_i,k)=1，\gcd(p_i,p_j)=1$，指对于任意 $p_i$，均属于质因数且与其他数 $p_j$ 互质，简称质因数两两互质，即质因数均不相同 。

1.3 莫比乌斯函数性质

性质 1

$$\sum_{d|n}\mu(d)=[n=1]$$

tip：$d|n$ 表示能被 $n$ 整除的 $d$。$[n=1]$ 指 $n=1$ 则值为 $1$，否则为 $0$。

来自百度百科的证明：

1. 当 $n=1$ 时易证。
2. 当 $n \ne 0$ 时，不妨令 $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_k^{a_k}$。易证：在 $n$ 的所有因子中，莫比乌斯值不为 $0$ 的只有质因子次数为 $1$ 的因子，而质因子次数为 $a$ 的因子有 $C_k^r$ 个。$\therefore \sum\limits_{d|n} \mu(n)=C_k^0 - C_k^1 + C_k^2 +...+ (-1)^k C_k^k=\sum\limits_{i=0}^k(-1)^i C_k^i$

性质 2 ？

Part 2 莫比乌斯反演

2.1 芝士：欧拉函数

$$\varphi(n)=\sum_{i=1}^{n}[\gcd(n,i)=1]$$ $$\sum_{d|n}\varphi(n)=n$$

来自 OI wiki 的证明： 如果 $\gcd(k,n)=d$，那么 $\gcd(\frac{k}{d},\frac{n}{d})=1,(k<n)$。 不妨设 $f(x)$ 表示 $\gcd{k,n}=x$ 的数的个数，那么 $n=\sum\limits_{i=1}^{n}f(i)$。 根据上面证明，我们注意到，$f(x)=\varphi(\frac{n}{x})$，从而 $n=\sum\limits_{d|n}\varphi(\frac{n}{d})$。再次注意到，约数 $d$ 和 $\frac{n}{d}$ 具有对称性，所以 $n=\sum\limits_{d|n} \varphi (d)$。

2.2 莫比乌斯反演及其证明

$$g(n)=\sum_{d|n} f(d)\Longleftrightarrow f(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)$$ $$\sum_{p|\gcd(i,j)}\mu(p)=[\gcd(i,j)=1]$$ $$g(n)=\sum_{d|n}g(d)\mu \left (\frac{n}{d} \right)=\sum_{d|n,t|\frac{n}{d}}g(t)\mu\left(\frac{n}{d}\right)=\sum_{t|n}g(t)\sum_{d|\frac{n}{d}}\mu(d)=g(n)$$

2.3 性质 2

2.4 莫比乌斯反演经典例题

Ex.1 LuoguP3455 ZAP-Queries

题意简述

解题思路

$$\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}[\gcd(i,j)=1]$$ $$\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{p|\gcd(i,j)}\mu{(p)}$$ $$\sum_{p=1}^{\lfloor \frac {a}{d} \rfloor}\mu{(p)} \times {\lfloor \frac{a}{dp} \rfloor}\times{\lfloor \frac{b}{dp} \rfloor}$$

Ex.2 LuoguP2257 YY的GCD

题意简述

解题思路

$$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j) \in prime]=\sum_{k=1}^{n}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k](k\in prime)$$ $$\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}[\gcd(i,j)=1](k\in prime)$$ $$\sum_{k=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}\sum_{d|\gcd(i,j)}\mu(d)(k\in prime)$$ $$\sum_{k=1}^n\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\times\lfloor\frac{n}{kd}\rfloor\times\lfloor\frac{m}{kd}\rfloor(k \in prime)$$ $$\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k}\rfloor}\mu(d)\times \lfloor \frac{n}{T}\rfloor\times \lfloor \frac{m}{T}\rfloor (k \in prime)$$ $$\sum_{T=1}^n\lfloor \frac{n}{T}\rfloor\times\lfloor\frac{m}{T}\rfloor \sum_{k|T,k \in prime} \mu \left( \frac{T}{k} \right)$$

Ex.3 LuoguP3327 约数个数和

题意简述

解题思路

$$\begin{matrix} d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \\ \therefore \sum\limits_{i=1}^n\sum\limits_{j=1}^md(ij)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \end{matrix}$$ $$\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor [\gcd(x,y)=1]$$ $$\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor \sum\limits_{d|\gcd(x,y)}\mu(d)$$ $$\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m} \lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y} \rfloor \sum\limits_{d=1}^n\mu(d)\times[d|\gcd(x,y)]$$ $$\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx}\rfloor \lfloor \frac{m}{dy} \rfloor \sum\limits_{d=1}^n\mu(d)$$ $$\sum\limits_{d=1}^n\mu(d) \left(\sum\limits_{x=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{dx}\rfloor\right)\left(\sum\limits_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{m}{dy} \rfloor \right)$$

Ex.4 LuoguP1829 Crash的数字表格

题意简述

$\operatorname{lcm}(i,j)$ 指 $i$ 和 $j$ 的最小公倍数。

解题思路

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\operatorname{lcm}(i,j)=\sum_{i=1}^n\sum_{j=1}^m\frac{i\cdot j}{\gcd(i,j)}=\sum\limits_{d=1}^n\sum\limits_{i=1}^n\sum\limits_{j=1}^m \frac{i\times j}{d} [\gcd(i,j)=d]$$ $$\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}[\gcd(i,j)=1]$$ $$\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor} {i\times j\times d}\sum\limits_{k|\gcd(i,j)}\mu(k)$$ $$\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{d} \rfloor}i[\gcd(k,i)=1]\sum\limits_{j=1}^{\lfloor \frac{m}{d} \rfloor}j[\gcd(k,j)=1]$$ $$\sum\limits_{d=1}^nd\sum\limits_{k=1}^n\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}ik\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}jk$$ $$\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\sum\limits_{i=1}^{\lfloor \frac{n}{dk} \rfloor}i\sum\limits_{j=1}^{\lfloor \frac{m}{dk} \rfloor}j$$ $$\begin{align*} &\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor(\lfloor \frac{n}{dk} \rfloor + 1)}{2}\times \frac{\lfloor \frac{m}{dk} \rfloor(\lfloor \frac{m}{dk} \rfloor + 1)}{2} \\ =&\sum\limits_{d=1}^nd\sum\limits_{k=1}^nk^2\mu(k)\times \frac{\lfloor \frac{n}{dk} \rfloor \lfloor \frac{m}{dk} \rfloor (\lfloor \frac{n}{dk} \rfloor + 1) (\lfloor \frac{m}{dk} \rfloor + 1)}{4} \end{align*}$$ $$\begin{array}{c} \sum\limits_{x=1}^nx\sum\limits_{k|x}k\mu(k)\times \frac{\lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{x} \rfloor (\lfloor \frac{n}{x} \rfloor + 1) (\lfloor \frac{m}{x} \rfloor + 1)}{4} \end{array}$$ $$\begin{align*} \therefore g\left(\prod P_i^{a_i}\right)&=\prod g\left(P_i^{a_{i}}\right) \\ &=\prod\left(x\times P_{i^0}\times \mu(1) +x\times P_{i}\times\mu\left(P_i\right) \right) \\ &=\prod\left((1-P_{i})x\right) \\ \end{align*}$$ $$\therefore g(p)=1-p \\ g(p^k)=g(p^{k-1}) \\$$ $$g(np)=g(n)\times g(p)$$

Part 3 总结