自动搬运

查看原文

来自洛谷，原作者为

	smqa 내가 사는 이유 너니까/enfp-t

搬运于2025-08-24 22:48:50，当前版本为作者最后更新于2024-06-20 22:14:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目

首先发现是求 $[l,r]$ 之间的答案，所以我们前缀和一下，输出 $ans_r-ans_{l-1}$ 即可。

因为最终要向下取整，容易发现 $y$ 是正数还是实数没有什么区别，由此知道如果 $y$ 能被表示，那一定是由 $x_i$ 的倍数凑出来的。

假设我们要求 $ans_p$，应二分得到最大的 $q_{max}$ 满足

$$\lfloor \frac {q_{max}} {x_1} \rfloor+\lfloor \frac {q_{max}} {x_2} \rfloor+\cdots + \lfloor \frac {q_{max}} {x_n} \rfloor \le p $$

由此，$[1,p]$ 中的每一个可以被表示的数都可以被 $[1,q_{max}](q∈N_+)$ 中的数表示。

---

由于 $[1,q](q∈N_+)$ 中的数可能会表示出重复的数，所以我们进行容斥：

设两个不同的数 $q_1,q_2 (q_1 \lt q_2)$ 表示出了相同的数。

在随意两个不同的数的限制下（即 $q_1,q_2 (q_1 \lt q_2)$ 表示出的数字可以不同时），对于 $\forall i∈[1,n]$ 来说，$\lfloor \frac {q_1} {x_i} \rfloor \le \lfloor \frac {q_2} {x_i} \rfloor$。

而为了使它相同，我们要求对于 $\forall i∈[1,n]$ 来说，$\lfloor \frac {q_1} {x_i} \rfloor = \lfloor \frac {q_2} {x_i} \rfloor$。

此时会发现假设有一个 $q$ 且对于 $\forall i∈[1,n]$ 来说，$x_i \nmid q$，则这个 $q$ 没有意义，因为一定有另一个数 $q_{new}$ 保证 $\exist i∈[1,n] \ x_i | q_{new}$，且与 $q$ 表示出一样的数。

原因：下取整后剩下的数一定是 $x_i$ 的倍数，所以分子上的数只需要是 $x_i$ 的倍数即可。

此时将问题转换成 $[1,q_{max}]$ 中 $x_i$ 的倍数有多少。

首先是容斥的基本式子：

$$|\bigcup_{i=1}^nA_i|=\sum_{i=1}^n|A_i|-\sum_{i,j: \ 1 \le i \lt j \le n}|A_i \cap A_j|+\sum_{i,j,k: \ 1 \le i \lt j \lt k\le n}|A_i \cap A_j \cap A_k|- \cdots +(-1)^{n-1}|A_1 \cap \cdots \cap A_n| $$

这个式子可以进行化简，假设 $B$ 表示含有所有 $A_i$ 的集合，则式子变为：

$$|\bigcup_{i=1}^nA_i|=\sum_{C \subseteq B} (-1)^{|C|-1} |\bigcap_{e∈C} e| $$

综上，本题的式子也就呼之欲出。

设 $K$ 表示所有 $x_i$ 表示的集合，答案如下。

$$\sum_{s\subseteq K}(-1)^{|K|-1} \lfloor \frac {q_{max}} {lcm \ s} \rfloor $$

代码不放了。

---

题外话：

yzr 和 zhy！仙品！金婚！纯爱！爽！

（为了说题外话我写了一整篇题解，管理员大大求过）