维什戴尔也能看懂的莫反和杜教筛（？

· · 个人记录

0x00 定义

积性函数定义为满足 \forall x,y,\gcd(x,y)=1，有 f(x)f(y)=f(xy) 的函数.

$$ \mu(x)=\begin{cases}1&x=1\\0&x\ \textsf{存在平方因子}\\(-1)^{\omega(x)}&\textsf{otherwise}\end{cases} $$ $\omega(x)$ 表示 $x$ 的本质不同质因子个数. $\varepsilon$ 为单位函数，$\varepsilon(n)=[n=1]$. $1$ 为常数函数，$1(n)=1$. $\mathrm{id}_k$ 为恒等函数，$\mathrm{id}_k(n)=n^k$. $\sigma$ 为除数函数，$\sigma_k(n)=\sum\limits_{d\mid n}d^k$. $\sigma_0(n)$ 记为 $d(n)$. $\varphi$ 为欧拉函数，$\varphi(n)=\sum\limits_{i=1}^n [\gcd(i,n)=1]$. 以上均为积性函数. ### 0x01 Dirichlet 卷积 两个数论函数 $f(x)$ 和 $g(x)$，定义其 Dirichlet 卷积 $f*g$ 为： $$ (f*g)(x)=\sum\limits_{d\mid x}f(d)g(\dfrac{x}{d}) $$ 即 $f(x)$ 和 $g(y)$ 的乘积贡献到 $(f*g)(xy)$ 中. Dirichlet 卷积具有以下性质： - 交换律：$f*g=g*f$. - 结合律：$(f*g)*h=f*(g*h)$. - 分配律：$(f+g)*h=f*h+g*h$. - 单位元：$f*\varepsilon=f$. 我们有：$\mu*1=\varepsilon,\varphi*1=\mathrm{id}$. ::::info[证明 $\mu*1=\varepsilon$] 首先有：$(\mu*1)(n)=\sum\limits_{d\mid n}\mu(d)1(\dfrac{n}{d})=\sum\limits_{d\mid n}\mu(d)$. 即我们需要证明：$\sum\limits_{d\mid n}\mu(d)=[n=1]$. 对于 $n=1$，原式 $=\mu(1)=1$. 对于 $n>1$，考虑将 $n$ 质因数分解为 $n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\cdots p_{\omega(n)}^{k_{\omega(n)}}$，显然若需要让 $\mu(d)\ne 0$，$d$ 只能是让 $p_i$ 选 $0$ 或 $1$ 个，枚举选了 $i$ 个不同的 $p$，显然此时 $\mu(d)=(-1)^i$，$d$ 有 $\binom{\omega(n)}{i}$ 种选法，则有： $$ \sum\limits_{d\mid n}\mu(d)=\sum\limits_{i=1}^{\omega(n)}\binom{\omega(n)}{i}(-1)^i $$ 这是一个非常明显的二项式的形式，用二项式定理可得后面的部分为 $(1-1)^{\omega(n)}=0$，因此对于 $n>1,\sum\limits_{d\mid n}\mu(d)=0$. 得证. :::: ### 0x02 莫比乌斯反演 如果我们知道了 $f*1=g$ 和 $g$，根据前面的 $\mu*1=\varepsilon$ 以及 $f*\varepsilon=f$，我们有： $$ \begin{aligned} f*1&=g\\ f*1*\mu&=g*\mu\\ f*\varepsilon&=g*\mu\\ f&=g*\mu \end{aligned} $$ $g$ 称为 $f$ 的莫比乌斯变换，$f$ 称为 $g$ 的莫比乌斯反演. 然后莫反的一个常见用途是做形如 $[\gcd(x,y)=1]$ 这类限制的. 根据定义和 $\mu*1=\varepsilon$，上面这个就可以写成 $\sum\limits_{d\mid \gcd(x,y)}\mu(d)$ 或者 $\sum\limits_{d\mid x,d\mid y}\mu(d)$. 然后我们也可以证明前面的 $\varphi*1=\mathrm{id}$ 了. :::info[证明] 我们有：$(\varphi*1)(n)=\sum\limits_{d\mid n}\varphi(d)$. $$ \begin{aligned} \sum\limits_{d\mid n}\varphi(d) &=\sum\limits_{d\mid n}\sum\limits_{i=1}^d[\gcd(i,d)=1]\\ &=\sum\limits_{d\mid n}\sum\limits_{i=1}^d\sum\limits_{j\mid \gcd(i,d)}\mu(j)\\ &=\sum\limits_{d\mid n}\sum\limits_{j\mid d}\mu(j)\sum\limits_{i=1}^\tfrac{d}{j}&\textsf{此时}\ i\cdot j\ \textsf{为前面的}\ i. \\ &=\sum\limits_{d\mid n}\sum\limits_{j\mid d}\mu(j)\dfrac{d}{j}\\ &=\sum\limits_{j\mid n}\mu(j)\sum\limits_{k\mid\tfrac{n}{j}}k&\textsf{令 }d=j\cdot k\\ &=\sum\limits_{j\mid n}\mu(j)\sigma(\dfrac{n}{j}) \end{aligned} $$ 即：$\varphi*1=\mu*\sigma$. 可以发现，根据 $\sigma(n)=\sum\limits_{d\mid n}d$ 的定义，我们有 $\sigma=\mathrm{id}*1$. 则有：$\varphi*1=\mu*(\mathrm{id}*1)=(\mu*1)*\mathrm{id}=\varepsilon*\mathrm{id}=\mathrm{id}$. ::: ### 0x03 一些经典题 就这类题目的 trick 基本上是把 $\gcd$ 提出来，提成 $[\gcd(x,y)=1]$ 的形式然后用前面的方法做. ::::info[[P3911](https://www.luogu.com.cn/problem/P3911)] 给定 $n$，长度为 $n$ 的序列 $a$，求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n \mathrm{lcm}(a_i,a_j)$. :::info[Sol] 大力推柿子. 先令 $c_i$ 表示 $a$ 中等于 $i$ 的数的个数，$V$ 为值域. $$ \begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^n\mathrm{lcm}(a_i,a_j) &=\sum\limits_{i=1}^V\sum\limits_{j=1}^V \mathrm{lcm}(i,j)c_ic_j\\ &=\sum\limits_{i=1}^V\sum\limits_{j=1}^V\dfrac{ij}{\gcd(i,j)}c_ic_j\\ &=\sum\limits_{d=1}^V\sum\limits_{i=1}^V\sum\limits_{j=1}^V[\gcd(i,j)=d]\dfrac{ij}{d}c_ic_j\\ &=\sum\limits_{d=1}^V\sum\limits_{i=1}^{\left\lfloor\tfrac{V}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{V}{d}\right\rfloor}[\gcd(i,j)=1]i\cdot j\cdot d\cdot c_{id}\cdot c_{jd}&i\gets \dfrac{i}{d},j\gets \dfrac{j}{d}\\ &=\sum\limits_{d=1}^V\sum\limits_{i=1}^{\left\lfloor\tfrac{V}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{V}{d}\right\rfloor}\sum\limits_{k\mid \gcd(i,j)}\mu(k)\cdot i\cdot j\cdot d\cdot c_{id}\cdot c_{jd}\\ &=\sum\limits_{d=1}^V\sum\limits_{k=1}^{\left\lfloor\tfrac{V}{d}\right\rfloor}\mu(k)\sum\limits_{i=1}^{\left\lfloor\tfrac{V}{kd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{V}{kd}\right\rfloor}i\cdot j\cdot d\cdot k^2\cdot c_{idk}\cdot c_{jdk}&\textsf{提出}\ k,i\gets\dfrac{i}{k},j\gets\dfrac{j}{k}\\ \textsf{令}\ T=kd\textsf{，}\\ &=\sum\limits_{T=1}^VT\sum\limits_{k\mid T}\mu(k)\cdot k\sum\limits_{i=1}^{\left\lfloor\tfrac{V}{T}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{V}{T}\right\rfloor}i\cdot j\cdot c_{iT}\cdot c_{jT}\\ \end{aligned} $$ 容易发现，右边这个式子组合意义是选两个物品（可相同），选第 $i$ 个权值为 $i\cdot c_{iT}$，求所有方案权值和，这个显然直接平方即可. 即： $$ \begin{aligned} \textsf{原式}&=\sum\limits_{T=1}^VT\sum\limits_{k\mid T}\mu(k)\cdot k\left(\sum\limits_{i=1}^{\left\lfloor\tfrac{V}{T}\right\rfloor}i\cdot c_{iT}\right)^2 \end{aligned} $$ 左边预处理，右边直接算，复杂度调和级数. ::: :::: ::::info[[P3312](https://www.luogu.com.cn/problem/P3312)] 有一张 $n\times m$ 的矩阵 $a$，有 $a_{i,j}=\sum\limits_{d\mid i,d\mid j}d$。多次给定 $v$，求 $\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[a_{i,j}\le v]a_{i,j}\right)\bmod2^{31}$. :::info[Sol] 考虑如果不考虑后面的限制怎么求 $\sum a_{i,j}$. 有： $$ \begin{aligned} \sum\limits_{i=1}^n\sum\limits_{j=1}^ma_{i,j}&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d\mid i,d\mid j}d\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{d\mid \gcd(i,j)}d\\ &=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma(\gcd(i,j))\\ &=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=d]\sigma(d)\\ &=\sum\limits_{d=1}^{\min(n,m)}\sigma(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=d]\\ &=\sum\limits_{d=1}^{\min(n,m)}\sigma(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}[\gcd(i,j)=1]\\ &=\sum\limits_{d=1}^{\min(n,m)}\sigma(d)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{d}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{d}\right\rfloor}\sum\limits_{k\mid \gcd(i,j)}\mu(k)\\ &=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{k=1}^{\left\lfloor\tfrac{\min(n,m)}{d}\right\rfloor}\sigma(d)\mu(k)\sum\limits_{i=1}^{\left\lfloor\tfrac{n}{kd}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\tfrac{m}{kd}\right\rfloor}\\ &=\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{k=1}^{\left\lfloor\tfrac{\min(n,m)}{d}\right\rfloor}\sigma(d)\mu(k)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor\\ &=\sum\limits_{T=1}^{\min(n,m)}\sum\limits_{d\mid T}\sigma(d)\mu(\dfrac{T}{d})\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor&\textsf{令}\ T=kd \end{aligned} $$ 然后显然对于询问 $v$，$a_{i,j}$ 有贡献当且仅当 $\sigma(d)\le v$. 然后这个左边仅和 $d,T,v$ 有关，右边和 $n,m$ 有关. 离线后按 $\sigma (d)$ 排序，把每次 $\sigma(d)\mu(\dfrac{T}{d})$ 贡献到 $d$ 的倍数即可. 查询就整除分块，左边是一个区间查询，右边 $O(1)$ 算，树状数组维护，复杂度 $O(n\ln n\log n+q\sqrt n\log n)$. ::: ::::