专栏文章

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

NNygglatho
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minuu1zm
此快照首次捕获于
2025/12/02 08:43
3 个月前
此快照最后确认于
2025/12/02 08:43
3 个月前
查看原文

0x00 定义

积性函数定义为满足 ∀x,y,gcd⁡(x,y)=1\forall x,y,\gcd(x,y)=1，有 f(x)f(y)=f(xy)f(x)f(y)=f(xy) 的函数.
μ\mu 为莫比乌斯函数，定义为：
μ(x)={1x=10x 存在平方因子(−1)ω(x)otherwise\mu(x)=\begin{cases}1&x=1\\0&x\ \textsf{存在平方因子}\\(-1)^{\omega(x)}&\textsf{otherwise}\end{cases}
ω(x)\omega(x) 表示 xx 的本质不同质因子个数.
ε\varepsilon 为单位函数，ε(n)=[n=1]\varepsilon(n)=[n=1].
11 为常数函数，1(n)=11(n)=1.
idk\mathrm{id}_k 为恒等函数，idk(n)=nk\mathrm{id}_k(n)=n^k.
σ\sigma 为除数函数，σk(n)=∑d∣ndk\sigma_k(n)=\sum\limits_{d\mid n}d^k. σ0(n)\sigma_0(n) 记为 d(n)d(n).
φ\varphi 为欧拉函数，φ(n)=∑i=1n[gcd⁡(i,n)=1]\varphi(n)=\sum\limits_{i=1}^n [\gcd(i,n)=1].
以上均为积性函数.

0x01 Dirichlet 卷积

两个数论函数 f(x)f(x) 和 g(x)g(x)，定义其 Dirichlet 卷积 f∗gf*g 为：
(f∗g)(x)=∑d∣xf(d)g(xd)(f*g)(x)=\sum\limits_{d\mid x}f(d)g(\dfrac{x}{d})
即 f(x)f(x) 和 g(y)g(y) 的乘积贡献到 (f∗g)(xy)(f*g)(xy) 中.
Dirichlet 卷积具有以下性质：
  • 交换律：f∗g=g∗ff*g=g*f.
  • 结合律：(f∗g)∗h=f∗(g∗h)(f*g)*h=f*(g*h).
  • 分配律：(f+g)∗h=f∗h+g∗h(f+g)*h=f*h+g*h.
  • 单位元：f∗ε=ff*\varepsilon=f.
我们有：μ∗1=ε,φ∗1=id\mu*1=\varepsilon,\varphi*1=\mathrm{id}.
证明 μ∗1=ε\mu*1=\varepsilon
首先有：(μ∗1)(n)=∑d∣nμ(d)1(nd)=∑d∣nμ(d)(\mu*1)(n)=\sum\limits_{d\mid n}\mu(d)1(\dfrac{n}{d})=\sum\limits_{d\mid n}\mu(d).
即我们需要证明：∑d∣nμ(d)=[n=1]\sum\limits_{d\mid n}\mu(d)=[n=1].
对于 n=1n=1，原式 =μ(1)=1=\mu(1)=1.
对于 n>1n>1，考虑将 nn 质因数分解为 n=p1k1p2k2p3k3⋯pω(n)kω(n)n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\cdots p_{\omega(n)}^{k_{\omega(n)}}，显然若需要让 μ(d)≠0\mu(d)\ne 0，dd 只能是让 pip_i 选 00 或 11 个，枚举选了 ii 个不同的 pp，显然此时 μ(d)=(−1)i\mu(d)=(-1)^i，dd 有 (ω(n)i)\binom{\omega(n)}{i} 种选法，则有：
∑d∣nμ(d)=∑i=1ω(n)(ω(n)i)(−1)i\sum\limits_{d\mid n}\mu(d)=\sum\limits_{i=1}^{\omega(n)}\binom{\omega(n)}{i}(-1)^i
这是一个非常明显的二项式的形式，用二项式定理可得后面的部分为 (1−1)ω(n)=0(1-1)^{\omega(n)}=0，因此对于 n>1,∑d∣nμ(d)=0n>1,\sum\limits_{d\mid n}\mu(d)=0.
得证.

0x02 莫比乌斯反演

如果我们知道了 f∗1=gf*1=g 和 gg，根据前面的 μ∗1=ε\mu*1=\varepsilon 以及 f∗ε=ff*\varepsilon=f，我们有：
f∗1=gf∗1∗μ=g∗μf∗ε=g∗μf=g∗μ\begin{aligned} f*1&=g\\ f*1*\mu&=g*\mu\\ f*\varepsilon&=g*\mu\\ f&=g*\mu \end{aligned}
gg 称为 ff 的莫比乌斯变换，ff 称为 gg 的莫比乌斯反演.
然后莫反的一个常见用途是做形如 [gcd⁡(x,y)=1][\gcd(x,y)=1] 这类限制的.
根据定义和 μ∗1=ε\mu*1=\varepsilon，上面这个就可以写成 ∑d∣gcd⁡(x,y)μ(d)\sum\limits_{d\mid \gcd(x,y)}\mu(d) 或者 ∑d∣x,d∣yμ(d)\sum\limits_{d\mid x,d\mid y}\mu(d).
然后我们也可以证明前面的 φ∗1=id\varphi*1=\mathrm{id} 了.
证明
我们有：(φ∗1)(n)=∑d∣nφ(d)(\varphi*1)(n)=\sum\limits_{d\mid n}\varphi(d).
∑d∣nφ(d)=∑d∣n∑i=1d[gcd⁡(i,d)=1]=∑d∣n∑i=1d∑j∣gcd⁡(i,d)μ(j)=∑d∣n∑j∣dμ(j)∑i=1dj此时 i⋅j 为前面的 i.=∑d∣n∑j∣dμ(j)dj=∑j∣nμ(j)∑k∣njk令 d=j⋅k=∑j∣nμ(j)σ(nj)\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}
即：φ∗1=μ∗σ\varphi*1=\mu*\sigma.
可以发现，根据 σ(n)=∑d∣nd\sigma(n)=\sum\limits_{d\mid n}d 的定义，我们有 σ=id∗1\sigma=\mathrm{id}*1.
则有：φ∗1=μ∗(id∗1)=(μ∗1)∗id=ε∗id=id\varphi*1=\mu*(\mathrm{id}*1)=(\mu*1)*\mathrm{id}=\varepsilon*\mathrm{id}=\mathrm{id}.

0x03 一些经典题

就这类题目的 trick 基本上是把 gcd⁡\gcd 提出来，提成 [gcd⁡(x,y)=1][\gcd(x,y)=1] 的形式然后用前面的方法做.
P3911
给定 nn，长度为 nn 的序列 aa，求 ∑i=1n∑j=1nlcm(ai,aj)\sum\limits_{i=1}^n\sum\limits_{j=1}^n \mathrm{lcm}(a_i,a_j).
Sol
大力推柿子.
先令 cic_i 表示 aa 中等于 ii 的数的个数，VV 为值域.
∑i=1n∑j=1nlcm(ai,aj)=∑i=1V∑j=1Vlcm(i,j)cicj=∑i=1V∑j=1Vijgcd⁡(i,j)cicj=∑d=1V∑i=1V∑j=1V[gcd⁡(i,j)=d]ijdcicj=∑d=1V∑i=1⌊Vd⌋∑j=1⌊Vd⌋[gcd⁡(i,j)=1]i⋅j⋅d⋅cid⋅cjdi←id,j←jd=∑d=1V∑i=1⌊Vd⌋∑j=1⌊Vd⌋∑k∣gcd⁡(i,j)μ(k)⋅i⋅j⋅d⋅cid⋅cjd=∑d=1V∑k=1⌊Vd⌋μ(k)∑i=1⌊Vkd⌋∑j=1⌊Vkd⌋i⋅j⋅d⋅k2⋅cidk⋅cjdk提出 k,i←ik,j←jk令 T=kd，=∑T=1VT∑k∣Tμ(k)⋅k∑i=1⌊VT⌋∑j=1⌊VT⌋i⋅j⋅ciT⋅cjT\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}
容易发现，右边这个式子组合意义是选两个物品（可相同），选第 ii 个权值为 i⋅ciTi\cdot c_{iT}，求所有方案权值和，这个显然直接平方即可.
即：
原式=∑T=1VT∑k∣Tμ(k)⋅k(∑i=1⌊VT⌋i⋅ciT)2\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}
左边预处理，右边直接算，复杂度调和级数.
P3312
有一张 n×mn\times m 的矩阵 aa，有 ai,j=∑d∣i,d∣jda_{i,j}=\sum\limits_{d\mid i,d\mid j}d。多次给定 vv，求 (∑i=1n∑j=1m[ai,j≤v]ai,j) mod 231\left(\sum\limits_{i=1}^n\sum\limits_{j=1}^m[a_{i,j}\le v]a_{i,j}\right)\bmod2^{31}.
Sol
考虑如果不考虑后面的限制怎么求 ∑ai,j\sum a_{i,j}.
有：
∑i=1n∑j=1mai,j=∑i=1n∑j=1m∑d∣i,d∣jd=∑i=1n∑j=1m∑d∣gcd⁡(i,j)d=∑i=1n∑j=1mσ(gcd⁡(i,j))=∑d=1min⁡(n,m)∑i=1n∑j=1m[gcd⁡(i,j)=d]σ(d)=∑d=1min⁡(n,m)σ(d)∑i=1n∑j=1m[gcd⁡(i,j)=d]=∑d=1min⁡(n,m)σ(d)∑i=1⌊nd⌋∑j=1⌊md⌋[gcd⁡(i,j)=1]=∑d=1min⁡(n,m)σ(d)∑i=1⌊nd⌋∑j=1⌊md⌋∑k∣gcd⁡(i,j)μ(k)=∑d=1min⁡(n,m)∑k=1⌊min⁡(n,m)d⌋σ(d)μ(k)∑i=1⌊nkd⌋∑j=1⌊mkd⌋=∑d=1min⁡(n,m)∑k=1⌊min⁡(n,m)d⌋σ(d)μ(k)⌊nkd⌋⌊mkd⌋=∑T=1min⁡(n,m)∑d∣Tσ(d)μ(Td)⌊nT⌋⌊mT⌋令 T=kd\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}
然后显然对于询问 vv，ai,ja_{i,j} 有贡献当且仅当 σ(d)≤v\sigma(d)\le v.
然后这个左边仅和 d,T,vd,T,v 有关，右边和 n,mn,m 有关.
离线后按 σ(d)\sigma (d) 排序，把每次 σ(d)μ(Td)\sigma(d)\mu(\dfrac{T}{d}) 贡献到 dd 的倍数即可.
查询就整除分块，左边是一个区间查询，右边 O(1)O(1) 算，树状数组维护，复杂度 O(nln⁡nlog⁡n+qnlog⁡n)O(n\ln n\log n+q\sqrt n\log n).

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...