伊埃斯的小站
日记

日记

Wed Jun 18 2025
8 label.readTime
life 日记
1445 label.wordCount

建议各大 OJ 加上切题防沉迷。

Problem b Link to

我们设 calc(n,m)=∑i=1n∑j=1m[gcd⁡(i,j)=k]calc(n,m) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j) = k]。那么这题的答案就是 calc(b,d)−calc(a−1,d)−calc(c−1,b)+calc(a−1,c−1)calc(b,d) - calc(a - 1,d) - calc(c - 1,b) + calc(a - 1,c - 1)。考虑如何求 calc(n,m)calc(n,m)。我们直接开始推柿子。

calc(n,m)=∑i=1n∑j=1m[gcd⁡(i,j)=k]=∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1]=∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)=∑d=1min⁡(n,m)μ(d)∑i=1⌊nk⌋[d∣i]∑j=1⌊md⌋[d∣j]=∑d=1min⁡(n,m)μ(d)⌊nkd⌋⌊mkd⌋\begin{aligned} calc(n,m) & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[\gcd(i,j) = k] \\ & = \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{{\lfloor \frac{m}{k} \rfloor}}[\gcd(i,j) = 1] \\ & = \sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}\sum_{j = 1}^{{\lfloor \frac{m}{k} \rfloor}}\sum_{d \mid \gcd(i,j)}\mu(d) \\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{k} \rfloor}[d \mid i]\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}[d \mid j] \\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\lfloor \frac{n}{kd} \rfloor\lfloor \frac{m}{kd} \rfloor \end{aligned}

然后我们就可以愉快的数论分块了，时间复杂度 O(n)O(\sqrt{n})。

但是这道沟槽题目还要卡常。。。

Crash的数字表格 / JZPTAB Link to

题意：求 ∑i=1n∑j=1mlcm⁡(i,j)\sum_{i = 1}^{n}\sum_{j = 1}^{m}\operatorname{lcm}(i,j)。讨厌小作文题面

于是我们继续推柿子：

calc(n,m)=∑i=1n∑j=1mlcm⁡(i,j)=∑i=1n∑j=1mijgcd⁡(i,j)=∑d=1min⁡(n,m)∑i=1n∑j=1mijd[d=gcd⁡(i,j)]=∑d=1min⁡(n,m)∑i=1n∑j=1mijd[d∣i][d∣j][gcd⁡(id,jd)=1]=∑d=1min⁡(n,m)∑i=1⌊nd⌋∑j=1⌊md⌋id×jdd[gcd⁡(i,j)=1]=∑d=1min⁡(n,m)∑i=1⌊nd⌋∑j=1⌊md⌋dij[gcd⁡(i,j)=1]=∑d=1min⁡(n,m)d∑i=1⌊nd⌋∑j=1⌊md⌋ij[gcd⁡(i,j)=1]\begin{aligned} calc(n,m) & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\operatorname{lcm}(i,j) \\ & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{\gcd(i,j)} \\ & = \sum_{d = 1}^{\min(n,m)}\sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{d}[d = \gcd(i,j)] \\ & = \sum_{d = 1}^{\min(n,m)}\sum_{i = 1}^{n}\sum_{j = 1}^{m}\frac{ij}{d}[d \mid i][d \mid j][\gcd(\frac{i}{d},\frac{j}{d}) = 1] \\ & = \sum_{d = 1}^{\min(n,m)}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}\frac{id \times jd}{d}[\gcd(i,j) = 1] \\ & = \sum_{d = 1}^{\min(n,m)}\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}dij[\gcd(i,j) = 1] \\ & = \sum_{d = 1}^{\min(n,m)}d\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}ij[\gcd(i,j) = 1] \\ \end{aligned}

设 f(n,m)=∑i=1n∑j=1mij[gcd⁡(i,j)=1]f(n,m) = \sum_{i = 1}^{n}\sum_{j = 1}^{m}ij[\gcd(i,j) = 1]，那么 calc(n,m)=∑d×f(⌊nd⌋,⌊md⌋)calc(n,m) = \sum d \times f(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)，依然是数论分块。现在我们尝试求解 f(n,m)f(n,m)。

f(n,m)=∑i=1n∑j=1mij[gcd⁡(i,j)=1]=∑i=1n∑j=1mij∑d∣gcd⁡(i,j)μ(d)=∑d=1min⁡(n,m)μ(d)∑i=1n[d∣i]∑j=1m[d∣j]⋅ij=∑d=1min⁡(n,m)μ(d)∑i=1⌊nd⌋∑j=1⌊md⌋id×jd=∑d=1min⁡(n,m)d2μ(d)∑i=1⌊nd⌋∑j=1⌊md⌋ij=∑d=1min⁡(n,m)d2μ(d)∑i=1⌊nd⌋i∑j=1⌊md⌋j\begin{aligned} f(n,m) & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}ij[\gcd(i,j) = 1] \\ & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}ij\sum_{d \mid \gcd(i,j)}\mu(d) \\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^{n}[d \mid i]\sum_{j = 1}^{m}[d \mid j] \cdot ij \\ & = \sum_{d = 1}^{\min(n,m)} \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}id \times jd \\ & = \sum_{d = 1}^{\min(n,m)}d^2 \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}ij \\ & = \sum_{d = 1}^{\min(n,m)}d^2 \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}i\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}j \end{aligned}

我们发现 ∑d=1min⁡(n,m)d2μ(d)\sum_{d = 1}^{\min(n,m)}d^2 \mu(d) 可以预处理前缀和，∑i=1⌊nd⌋i\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}i 和 ∑j=1⌊md⌋j\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}j 其实就是俩等差数列求和，O(1)O(1) 算就是了。于是我们就能够通过数论分块愉快的求解 f(n,m)f(n,m)，再套一层数论分块就能愉快的求解 calc(n,m)calc(n,m) 了。时间复杂度 O(n+m)O(n + m)。

ZAP-Queries Link to

其实就是 Problem b的弱化版。

已经没有什么好害怕的了 Link to

现在感觉二项式反演十分的和蔼可亲。

我们先令 k=n+k2k = \frac{n + k}{2}，即恰好有 kk 个糖果比药片大。看起来就很像二项式反演啊。我们设 dpi,jdp_{i,j} 表示前 ii 对里有 jj 对满足条件。转移就有 dpi,j=dpi−1,j+(lsti−j+1)×dpi−1,j−1dp_{i,j} = dp_{i - 1,j} + (lst_i - j + 1) \times dp_{i - 1,j - 1}，其中 lstilst_i 表示将 a,ba,b 都从小到大排序之后，blstib_{lst_i} 是第一个比 aia_i 大的。于是我们就得到了 gi=(n−i)!×dpn,ig_i = (n - i)! \times dp_{n,i}，反演一下就可以得到 fkf_k 了。

小星星 Link to

这里还窜出来个子集反演。

其实所有反演的本质都是容斥原理。

子集反演还没学所以这个题目就不写了。

算术 Link to

这个柿子是真的推不来。

我们发现 μ(lcm⁡(x,y))=μ(x)μ(y)μ(gcd⁡(x,y))\mu(\operatorname{lcm}(x,y)) = \mu(x) \mu(y) \mu(\gcd(x,y))，于是就是并不愉快的推柿子时间。

calc(n,m)=∑i=1n∑j=1mμ(lcm⁡(x,y))=∑i=1n∑j=1mμ(x)μ(y)μ(gcd⁡(x,y))=∑d=1min⁡(n,m)∑i=1n[d∣i]∑j=1n[d∣j]⋅μ(i)μ(j)μ(d)[gcd⁡(id,jd)=1]=∑d=1min⁡(n,m)μ(d)∑i=1⌊nd⌋∑j=1⌊md⌋μ(i⋅d)μ(j⋅d)[gcd⁡(i,j)=1]=∑d1=1min⁡(n,m)μ(d1)∑i=1⌊nd1⌋∑j=1⌊md1⌋μ(i⋅d1)μ(j⋅d1)∑d2∣gcd⁡(i,j)μ(d2)=∑d1=1min⁡(n,m)μ(d1)∑d2=1⌊min⁡(n,m)d1⌋μ(d2)∑i=1⌊nd1⌋[d2∣i]∑j=1⌊md1⌋[d2∣j]⋅μ(i⋅d1)μ(j⋅d1)=∑d1=1min⁡(n,m)μ(d1)∑d2=1⌊min⁡(n,m)d1⌋μ(d2)∑i=1⌊nd1d2⌋∑j=1⌊md1d2⌋μ(i⋅d1d2)μ(j⋅d1d2)\begin{aligned} calc(n,m) & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\mu(\operatorname{lcm}(x,y)) \\ & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\mu(x) \mu(y) \mu(\gcd(x,y)) \\ & = \sum_{d = 1}^{\min(n,m)}\sum_{i = 1}^{n}[d \mid i]\sum_{j = 1}^{n}[d \mid j] \cdot \mu(i) \mu(j) \mu(d) [\gcd(\frac{i}{d},\frac{j}{d}) = 1]\\ & = \sum_{d = 1}^{\min(n,m)} \mu(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}\mu(i \cdot d) \mu(j \cdot d)[\gcd(i,j) = 1] \\ & = \sum_{d_1 = 1}^{\min(n,m)} \mu(d_1) \sum_{i = 1}^{\lfloor \frac{n}{d_1} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d_1} \rfloor}\mu(i \cdot d_1) \mu(j \cdot d_1)\sum_{d_2 \mid \gcd(i,j)}\mu(d_2) \\ & = \sum_{d_1 = 1}^{\min(n,m)}\mu(d_1)\sum_{d_2 = 1}^{\lfloor \frac{\min(n,m)}{d_1}\rfloor}\mu(d_2)\sum_{i = 1}^{\lfloor \frac{n}{d_1} \rfloor}[d_2 \mid i]\sum_{j = 1}^{\lfloor \frac{m}{d_1} \rfloor}[d_2 \mid j] \cdot \mu(i \cdot d_1)\mu(j \cdot d_1) \\ & = \sum_{d_1 = 1}^{\min(n,m)}\mu(d_1)\sum_{d_2 = 1}^{\lfloor \frac{\min(n,m)}{d_1}\rfloor}\mu(d_2)\sum_{i = 1}^{\lfloor \frac{n}{d_1 d_2} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{d_1 d_2} \rfloor}\mu(i \cdot d_1 d_2)\mu(j \cdot d_1 d_2) \end{aligned}

我们枚举 t=d1d2t = d_1 d_2，那么就有 calc(n,m)=∑t∑d=1min⁡(n,m)μ(d)μ(td)∑i=1⌊nt⌋∑j=1⌊mt⌋μ(i⋅t)μ(j⋅t)calc(n,m) = \sum_{t}\sum_{d = 1}^{\min(n,m)}\mu(d) \mu(\frac{t}{d})\sum_{i = 1}^{\lfloor \frac{n}{t} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{t} \rfloor}\mu(i \cdot t)\mu(j \cdot t)。∑t∑d=1min⁡(n,m)μ(d)μ(td)\sum_{t}\sum_{d = 1}^{\min(n,m)}\mu(d) \mu(\frac{t}{d}) 可以预处理，∑i=1⌊nt⌋∑j=1⌊mt⌋μ(i⋅t)μ(j⋅t)\sum_{i = 1}^{\lfloor \frac{n}{t} \rfloor}\sum_{j = 1}^{\lfloor \frac{m}{t} \rfloor}\mu(i \cdot t)\mu(j \cdot t) 可以暴力算。总复杂度是一个调和级数，O(nlog⁡n)O(n\log n)。

约数个数和 Link to

首先有结论：d(ij)=∑x∣i∑y∣j[gcd⁡(x,y)=1]d(ij) = \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y) = 1]。然后就是推柿子时间。

d(ij)=∑x∣i∑y∣j[gcd⁡(x,y)=1]=∑x∣i∑y∣j∑d∣gcd⁡(x,y)μ(d)=∑d=1min⁡(i,j)[d∣i][d∣j]⋅μ(d)∑x∣i[d∣x]∑y∣j[d∣y]=∑d=1min⁡(i,j)[d∣i][d∣j]⋅μ(d)∑x∣id∑y∣jd1=∑d=1min⁡(i,j)[d∣i][d∣j]⋅μ(d)×d(id)×d(jd)\begin{aligned} d(ij) & = \sum_{x \mid i}\sum_{y \mid j}[\gcd(x,y) = 1] \\ & = \sum_{x \mid i}\sum_{y \mid j}\sum_{d \mid \gcd(x,y)}\mu(d) \\ & = \sum_{d = 1}^{\min(i,j)}[d \mid i][d \mid j] \cdot \mu(d)\sum_{x \mid i}[d \mid x]\sum_{y \mid j}[d \mid y] \\ & = \sum_{d = 1}^{\min(i,j)}[d \mid i][d \mid j] \cdot \mu(d)\sum_{x \mid \frac{i}{d}}\sum_{y \mid \frac{j}{d}}1 \\ & = \sum_{d = 1}^{\min(i,j)}[d \mid i][d \mid j] \cdot \mu(d) \times d(\frac{i}{d}) \times d(\frac{j}{d}) \end{aligned}

将 d(ij)d(ij) 带回原式：

calc(n,m)=∑i=1n∑j=1m∑d=1min⁡(i,j)[d∣i][d∣j]μ(d)×d(id)×d(jd)=∑d=1min⁡(n,m)μ(d)∑i=1n[d∣i]∑j=1n[d∣j]×d(id)×d(jd)=∑d=1min⁡(n,m)μ(d)∑i=1⌊nd⌋d(i)∑j=1⌊md⌋d(j)\begin{aligned} calc(n,m) & = \sum_{i = 1}^{n}\sum_{j = 1}^{m}\sum_{d = 1}^{\min(i,j)}[d \mid i][d \mid j]\mu(d) \times d(\frac{i}{d}) \times d(\frac{j}{d}) \\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^{n}[d \mid i]\sum_{j = 1}^{n}[d \mid j] \times d(\frac{i}{d}) \times d(\frac{j}{d}) \\ & = \sum_{d = 1}^{\min(n,m)}\mu(d)\sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor}d(i)\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor}d(j) \end{aligned}

我们可以预处理 i∈[1,n]i \in [1,n] 的 d(i)d(i) 并计算前缀和，然后就可以愉快的数论分块了。

后日谈 Link to 后日谈

今天反演了一天，这公式打的我简直想死。不过倒是发现了反演的用途：都是把限制放宽，放到好求的状态，然后求出 gg 就能反演出 ff 了。

比如二项式反演：把“恰好”放宽成“至少”，就可以通过钦定几个元素的状态求出 gg。
比如莫比乌斯反演：[gcd⁡(i,j)=1]=∑d∣gcd⁡(i,j)μ(d)[\gcd(i,j) = 1] = \sum_{d \mid \gcd(i,j)}\mu(d)，就可以不用管死人 i,ji,j 是否互质了。

今天晚自习上课的时候才发现做了 99 道反演。于是写了一晚上的日记，码了一晚上的公式。希望以后 vjudge 出一个切题防沉迷。


Telegram
Douban
Reddit
Pocket