本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-24 16:40:10

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

1. $\displaystyle x\in[1,n],S\subseteq\bigcup_{i=1}^n\{i\},x\notin S$
2. $\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)$。
:::: 后面可能还会有添加。
咕咕咕。
:::::