CF585E Present for Vitalik the Philatelist 题解 / 狄利克雷卷积学习笔记

zrl123456 · 2025-09-24 16:40:10 · 题解

:::::info[题目基本信息] 考察：莫比乌斯函数，狄利克雷卷积（2900）。
题目简介：
给定 \{a_n\}，求满足条件的 (x,S) 个数：

\displaystyle x\in[1,n],S\subseteq\bigcup_{i=1}^n\{i\},x\notin S
\displaystyle\gcd_{i\in S}a_i>1,\gcd(\gcd_{i\in S}a_i,a_x)=1

数据范围：

2\le n\le 5\times 10^5
\forall i\in[1,n],2\le a_i\le 10^7
::::: 令 f_d 表示 \{a_n\} 中与 d 互质的数的个数，g_d 表示可重集 \displaystyle\bigcup_{i=1}^n\{a_i\} 的非空子集中最大公约数恰好为 d 的个数。那么最后答案就为 \displaystyle\sum_{i=2}^Vf_ig_i，其中 V 是 a_i 的值域。
先进行 f_d 的推导：
\begin{aligned}f_d&=\sum_{i=1}^V[\gcd(i,d)=1]t_i\\&=\sum_{i=1}^V\sum_{d_2\mid\gcd(i,d)}\mu(d_2)t_i\\&=\sum_{d_2\mid d}\mu(d_2)\sum_{d_2\mid i}t_i\end{aligned}
其中 t_i 表示 \{a_n\} 中 i 的出现次数，即 \displaystyle t_i=\sum_{j=1}^n[a_j=i]。
令 \displaystyle F_d=\sum_{d|i}t_i,F'(d)=\mu(d)F_d，那么 \displaystyle f_d=\sum_{d_2\mid d}F'(d_2)。
再对 g_d 推导：
不妨令 G_d 为可重集 \displaystyle\bigcup_{i=1}^n\{a_i\} 的非空子集中最大公约数为 d 的倍数个数，注意到 G_d=2^{F_d}-1。
那么就有 \displaystyle G_d=\sum_{d_2\mid d}g_{d_2}。

那么现在我们要求下面类型的式子：

b_i=\sum_{j\mid i}a_j

b_i=\sum_{i\mid j}a_j

注意到他们是狄利克雷卷积的形式。
:::::success[狄利克雷卷积] 模板题

我们考虑到我们可以在计算 b_i 时枚举 i 的因子进行容斥，这时时间复杂度就是子集枚举的复杂度，时间复杂度就为 \Theta(3^{\log_2n})=\Theta(n^{\log_23})，显然无法通过本题。
于是我们要优化我们的高维前缀和，我们考虑对于每一维做一次一维前缀和，然后正确性显然，但由于没有容斥所以时间复杂度在维数较高时大大降低。
此时，时间复杂度就为 \displaystyle\Theta(\sum_{p\in\text{prime},p\le n}\frac{n}{p})=\Theta(n\log\log n)，空间复杂度为 \Theta(n)。
::::: 同时注意到 \displaystyle G_d=\sum_{d_2\mid d}g_{d_2} 是已知 b 求 a 的，那么我们反着来做一遍差分即可。
时间复杂度为 \Theta(n+V\log\log V)，空间复杂度为 \Theta(n)。 :::::warning[坑点] 还是那句话：卡空间。 ::::: :::::success[一些其他题目] 1 号题目
::::success[讲解] 注意到 \displaystyle\lfloor\frac{i}{k}\rfloor\ne\lfloor\frac{i-1}{k}\rfloor 当且仅当 k\mid i，那么由于 \displaystyle b_k=\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor}，则我们对 \{b_n\} 差分可以发现（设序列 p 差分后序列为 p'）：

\begin{aligned}b'_k&=b_k-b_{k-1}\\&=(\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor})-(\sum_{i=1}^na_{\lfloor\frac{k-1}{i}\rfloor})\\&=\sum_{i=1}^na_{\lfloor\frac{k}{i}\rfloor}-a_{\lfloor\frac{k-1}{i}\rfloor}\\&=\sum_{i\mid k}a_{\frac{k}{i}}-a_{\frac{k}{i}-1}\\&=\sum_{i\mid k}a'_{\frac{k}{i}}\end{aligned}

所以 \{b'_n\} 是 \{a'_n\} 的狄利克雷卷积，直接套模板即可。
时间复杂度为 \Theta(n\log\log n)，空间复杂度为 \Theta(n)。
:::: 2 号题目
::::info[闲话] 被 DS 薄纱了...... :::: ::::success[讲解] 容易发现这道题的式子是有强制性要求转移顺序的，我们必须从前往后转移 b_i 才可以得到正确的答案，那么我们该怎么办呢？
注意到一个性质：

\displaystyle d\mid k,d\ne k\Rightarrow d\le\frac{k}{2}

这个性质启示我们倍增，或者叫二进制分组，将 2^k+1\sim 2^{k+1} 的分为一组（其中 k\in\mathbb N）。
在此前我们也遇到了许多类似分组处理的思想，比如：

CF710(EDU16) 题解中 F 题二进制分组。
后面应该还有，但我懒得翻 4 页的题解。

为了方便，我们令 \displaystyle b'_k=\sum_{p\mid k,p\ne k}b_p，注意到这是一个典型的狄利克雷卷积形式，所以我们直接上狄利克雷卷积即可。

下面是 DS 写的算法过程：

注意 DS 所写有一定错误，比如“对每个素数 p\le m”应为“对每个素数 p\le R”，“对 j 从 m 到 1 枚举”应为“对 j 从 1 到 m”。

时间复杂度为 \Theta(n\log\log n) 但常数比板子题大几倍，空间复杂度为 \Theta(n)。
:::: 后面可能还会有添加。
咕咕咕。
:::::