0. 前置知识
1. 狄利克雷卷积
定义
定义域为 \(\mathbb{N_+}\) 的函数称为数论函数。
对于两个数论函数 \(f,g\)，其狄利克雷卷积为 \(h(n)=\sum\limits_{d\mid n} f(d)g(\dfrac{n}{d})=\sum\limits_{ab=n} f(a)g(b)\)，简记为 \(h=f * g\)
性质
狄利克雷卷积具有以下性质：
交换律 ：\(f * g=g * f\)。
非常好感性理解，因为狄利克雷卷积是对称的。
证明：令 \(x=b,y=a\)，则\((f * g)(n)=\sum\limits_{ab=n} f(a)g(b)=\sum\limits_{ba=n}g(b)f(a)=\sum\limits_{xy=n}g(x)f(y)=(g * f)(n)\)。
故 \(f * g=g * f\)。
从这个证明可以得出，对于一般的卷积 \((f * g)(n)=\sum\limits_{a\oplus b=n} f(a)g(b)\)，若 \(\oplus\) 运算满足交换律，则 \(f * g\) 满足交换律。
结合律：\((f * g) * h=f * (g * h)\)
证明：
\[\begin{split} ((f * g) * h)(n)&=\sum\limits_{c\mid n}(f * g)\left(\frac{n}{c}\right)h(c) \\ &=\sum\limits_{c\mid n}\sum\limits_{ab=\frac{n}{c}}f(a)g(b)h(c) \\ &=\sum\limits_{c\mid n}\sum\limits_{(ab)c=n} f(a)g(b)h(c)\\ \end{split} \]此时 \(c\mid n\) 在第二个条件成立时一定成立。
\[\begin{split} &=\sum_{(ab)c=n}f(a)g(b)h(c)\\ &=\sum_{a(bc)=n}f(a)g(b)h(c)\\ &=(f * (g * h))(n) \end{split} \]同交换律一样，若 \(\oplus\) 具有结合律，则其对应的卷积也具有结合律。
分配律：\((f+g) * h=f * h+g * h\)
证明：
\[\begin{split} ((f+g) * h)(n)&=\sum\limits_{ab=n}(f+g)(a)h(b) \\ &=\sum\limits_{ab=n} f(a)h(b)+g(a)h(b) \\ &=\sum\limits_{ab=n} f(a)h(b)+\sum\limits_{ab=n} g(a)h(b) \\ &=(f * h)(n)+(g * h)(n) \\ \end{split} \]故 \((f+g) * h=f * h+g * h\)
等式的性质：\(f=g \iff f * h=g * h\)，其中 \(h(1)\not=0\)
\(f=g \Rightarrow f * h=g * h\) 显然，下证：\(f=g \Leftarrow f * h=g * h\)
证明：
考虑反证法。若 \(f\not=g\)，则必定存在一个 \(y\in\mathbb{N_+}\)，使得 \(\forall i<y,f(i)=g(i)\)，且 \(f(y)\not=g(y)\)。
设 \(r=f * h-g * h=(f-g) * h\)
则：
\[\begin{split} r(y)&=\sum_{d|y} (f(d)-g(d))h\left(\dfrac{n}{d}\right) \\ &=(f(y)-g(y))h(1) \\ &\not=0 \end{split}\]与 \(r(y)=(f * h)(y)-(g * h)(y)=0\) 矛盾。
证毕。
注：由于逆元存在，该结论是显然的。
单位元：即单位函数 \(\varepsilon(x)=[x=1]\) ，满足对于任意数论函数 \(f\)，有 \(f * \varepsilon=f\)。
逆元：对于任意数论函数 \(f\) 满足 \(f(1)\not=0\)，则存在数论函数 \(g\) 满足 \(f * g=\varepsilon\)。
显然，若逆元存在，必唯一。
考虑构造一个 \(g\)。\((f * g)(x)=\varepsilon(x)\)
\[\begin{split} (f * g)(n)&=\sum_{d\mid n} f(d)g\left(\frac{n}{d}\right) \\ &=\sum_{d\mid n,d\not=1}f(d)g\left(\frac{n}{d}\right)+g(n)f(1) \\ g(n)&=\dfrac{\varepsilon(n)-\sum_{d\mid n,d\not=1}f(d)g(\frac{n}{d})}{f(1)} \end{split} \]特别地，当 \(f\) 为积性函数时，\(f(1)=1\)，此时 \(g(n)=\varepsilon(n)-\sum_{d\mid n,d\not=1}f(d)g(\frac{n}{d})\)
为了简便，下将 \(f\) 的逆元记为 \(f^{-1}\)。（区别于反函数）
2. 积性函数
定义
若数论函数 \(f(x)\) 满足 \(f(1)=1\)，且 \(\forall n,m\in\mathbb{N^* },\gcd(n,m)=1,f(nm)=f(n)f(m)\)，则称 \(f(x)\) 是积性函数。
若数论函数 \(f(x)\) 满足 \(f(1)=1\)，且 \(\forall n,m\in\mathbb{N^* },f(nm)=f(n)f(m)\)，则称 \(f(x)\) 是完全积性函数。
常见的积性函数有：
- 单位函数 \(\varepsilon(x)=[x=1]\) （完全积性）
- 常函数 \(\mathbb{1}(x)=1\)（完全积性），为方便起见，用 \(I\) 替代。
- 恒等函数 \(\operatorname{id}_ k(x)=x^k\)（完全积性）(\(\operatorname{id}_0=I\))
- 除数函数 \(\sigma_k(x)=\sum_{d|x} d^k\)，其中 \(\sigma_0(x)\) 为 \(x\) 的约数个数，又记作 \(\tau(x)\)，\(\sigma_1(x)\) 为 \(x\) 的约数和，简记为 \(\sigma(x)\)。（\(\sigma_k=\operatorname{id}_ k * \ I\)）
- 莫比乌斯函数 \(\mu(x)=\begin{cases}1&x=1\\0&\exists d>1,d^2\mid x\\(-1)^{\omega(x)}&\text{otherwise}\end{cases}\)，其中 \(\omega(x)\) 为 \(x\) 中不同质因子的个数。（\(\mu * I=\varepsilon\)）
- 欧拉函数 \(\varphi(x)=\sum_{i=1}^n [\gcd(i,n)=1]\) 为 \(1\cdots x\) 中与 \(x\) 互质的数的个数。（\(\varphi=\mu * \operatorname{id}\) 或 \(\varphi * I =\operatorname{id}\)）
notes：
- \(\mu\) 是 \(I\) 的卷积逆，这在下面也会提到。
- 设 \(x=\prod_{i=1}^k p_i^{\alpha_i}\)，其中 \(\forall i,\alpha_i>0\) ，则 \(\varphi(x)=x\cdot \prod_ {i=1}^k(1-\dfrac{1}{p_i})\)，\(\tau(x)=\prod_ {i=1}^k (\alpha_i+1)\)，\(\sigma(x)=\prod_{i=1}^k \sum_ {j=0}^{\alpha_i} p_i^j\)，都可以用积性在得出质数幂的结果后推出。
性质
- 若 \(f(x),g(x)\) 为积性函数，则下列函数为积性函数：
- \(h(x)=f(x^k)\)
证明：设 \(\gcd(x,y)=1\)，则有 \(\gcd(x^k,y^k)=1\)，则 \(h(x)h(y)=f(x^k)f(y^k)=f((xy)^k)=h(xy)\)
- \(h(x)=f^k(x)\)
证明：设 \(\gcd(x,y)=1\)，则有，则 \(h(x)h(y)=f^k(x)f^k(y)=(f(x)f(y))^k=f^k(xy)=h(xy)\)
- \(h(x)=f(x)g(x)\)
证明：设 \(\gcd(x,y)=1\)，则\(h(x)h(y)=f(x)f(y)\cdot g(x)g(y)=f(xy)g(xy)=h(xy)\)
- 若 \(f(x),g(x)\) 为积性函数，则下列函数为积性函数：（重要）
- \(h=f * g\)
证明：设 \(\gcd(x,y)=1\)，则
\[\begin{split} h(x)h(y)&=\sum_{d_1\mid x} f(d_1)g\left(\dfrac{x}{d_1}\right) \cdot \sum_{d_2\mid y} f(d_2)g\left(\dfrac{y}{d_2}\right) \\ &=\sum_{d_1\mid x,d_2\mid y} f(d_1)f(d_2)g(d_1)g(d_2) \\ &=\sum_{d_1\mid x,d_2\mid y} f(d_1d_2)g\left(\dfrac{xy}{d_1d_2}\right) \\ &=\sum_{d\mid xy} \ \ \sum_{d_1\mid x,d_2\mid y,d_1d_2=d}f(d)y\left(\dfrac{xy}{d}\right) \\ &=\sum_{d\mid xy} 1\cdot f(d)y\left(\dfrac{xy}{d}\right) \\ &=\sum_{d\mid xy} f(d)y\left(\dfrac{xy}{d}\right) \\ &=h(xy) \end{split}\]- \(g\) 满足 \(f * g=\varepsilon\)
证明：\(g(x)=\varepsilon(x)-\sum_{d|x,d\not=1}f(d)g(\frac{x}{d})\)
设 \(\gcd(x,y)=1,x\leqslant y\)。
首先，\(\varepsilon(1)=f(1)g(1)=1,f(1)=1\Rightarrow g(1)=1\)。
使用数学归纳法。
-
\(xy=1\)，此时 \(g(xy)=g(1)=g(x)g(y)\)
-
\(xy>1\)，此时 \(\varepsilon(xy)=\varepsilon(x)\varepsilon(y)=0\)，若此时 \(\forall x'y'<xy\) 且 \((x',y')=1\) ,\(g(x'y')=g(x')g(y')\)
证毕。
由上述结论可知，积性函数卷积性函数仍是积性函数，积性函数卷非积性函数是非积性函数。
3. 莫比乌斯反演
莫比乌斯函数公式推导
莫比乌斯函数 \(\mu\) 定义为常量函数 \(I\) 的逆。
显然，\(\mu\) 是积性函数（见上一节末）。
由逆元公式有 \(\mu(x)=\varepsilon(x)-\sum_{d\mid x,d\not=x} \mu(d)\)
当 \(x=1\) 时，\(\mu(1)=1\)
当 \(x\not=1\) 时，\(\mu(x)=-\sum_{d\mid x,d\not=x} \mu(d)\)
(i) \(p\in \mathbb{P}\)，\(\mu(p)=-\mu(1)=-1\)
(ii) \(x=p^k(k\geq 2)\)，由归纳法可知 \(\mu(x)=0\)
由于 \(\mu\) 是积性函数，所以我们可以对 \(x\) 标准分解后将其 \(\mu\) 值相乘。
令 \(x=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\)，\(\mu(x)=\prod \mu(p_i^{\alpha_i})\)
故 \(\mu(x)=\begin{cases}1&x=1\\0&\exists d>1,d^2\mid x\\(-1)^{\omega(x)}&\text{otherwise}\end{cases}\)
这个 \(\mu\) 可以线性筛筛出来。
莫比乌斯反演公式
形式一：（最本质的式子）
由于 \(\mu * I=\varepsilon\) 得
\[\sum_{d\mid n} \mu(d)=[n=1] \]形式二：
设 \(f(n)=\sum\limits_{d\mid n} g(d)\)，则 \(g(n)=\sum\limits_{d\mid n} \mu(d)f(\frac{n}{d})\)
证明：这个很显然。\(f=g * I\Rightarrow f * \mu=g\)
和式证明：
\[\begin{aligned} g(n)&=\sum_{d\mid n} g(d)\sum_{c\mid \frac nd} \mu(c) \\ &=\sum_{c\mid n} \mu(c)\sum_{d\mid \frac nc} g(d) \\ &=\sum_{c\mid n} \mu(c)f\left(\frac nc\right) \end{aligned}\]形式三：
设 \(f(n)=\sum\limits_{n\mid d} g(d)\)，则 \(g(n)=\sum\limits_{n\mid d} \mu(\dfrac{d}{n})f(d)\)
这里的和式可以有上限，即只考虑 \(\leq lim\) 的数。
证明：
\[\begin{aligned} g(n)&=\sum_{n\mid d} g(d)\sum_{d'\mid \frac dn} \mu(d') \\ &=\sum_{n\mid d} g(d)\sum_{n\mid c,c\mid d} \mu(\frac cn) \\ &=\sum_{n\mid c} \mu(\frac cn) \sum_{d\mid c} g(c) \\ &=\sum_{n\mid c} \mu(\frac cn)f(c) \end{aligned}\]4.基础应用
莫比乌斯反演的题目常与整除分块同时出现。
例一
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m \left[(i,j)=1\right] \\ =&\sum_{i=1}^n\sum_{j=1}^m \sum_{d\mid (i,j)} \mu(d) \\ =&\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{i=1}^n \sum_{j=1}^m [d\mid i][d\mid j] \\ =&\sum_{d=1}^{\min(n,m)} \mu(d) \lfloor\frac nd\rfloor\lfloor \frac md\rfloor \end{aligned}\]求 \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m \left[(i,j)=1\right]\)
对于多组询问，可以预处理 \(\mu\) 之和，然后用整除分块做到 \(\mathcal O(n+T\sqrt n)\) 的复杂度。
例二
求 \(\varphi(n)\)
考虑到 \(\displaystyle\varphi(n)=\sum_{i=1}^n [(n,i)=1]\)
则
\[\begin{aligned} \varphi(n)&=\sum_{i=1}^n \sum_{d\mid (n,i)} \mu(d) \\ &=\sum_{d\mid n} \mu(d)\sum_{i=1}^n [d\mid i] \\ &=\sum_{d\mid n} \mu(d)\frac nd \\ &=(\mu * \operatorname{id})(n) \end{aligned}\]例三
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m (i,j) \\ =&\sum_{d=1}^n d\cdot \sum_{i=1}^{\lfloor \frac nd\rfloor} \mu(i)\cdot \lfloor\frac n{d\cdot i} \rfloor\lfloor\frac m{d\cdot i} \rfloor \\ =&\sum_{d=1}^n d\cdot \sum_{d\mid i}^{n} \mu\left(\frac id\right)\cdot \lfloor\frac n{i} \rfloor\lfloor\frac m{i} \rfloor \\ =&\sum_{i=1}^n \sum_{d\mid i} d\cdot \mu\left(\frac id\right)\cdot \lfloor\frac n{i} \rfloor\lfloor\frac mi \rfloor \\ =& \sum_{i=1}^n \varphi(i)\cdot \lfloor \frac ni \rfloor \lfloor \frac mi \rfloor \end{aligned}\]求 \(\displaystyle \sum_{i=1}^n\sum_{j=1}^m (i,j)\)
可以发现，这个式子与例一的区别在于将 \(\mu\) 换成了 \(\varphi\)
标签：frac,函数,狄利克,卷积,sum,mid,mu,反演,xy From： https://www.cnblogs.com/pref-ctrl27/p/16600639.html