题解 P9489【ZHY 的表示法】

发布时间 2023-08-01 22:06:44作者: rui_er

容易想到将所求差分,变为 \([1,r]\) 的答案减去 \([1,l-1]\) 的答案。

直觉告诉我们所谓的“实数 \(y\)”就是没事闲的,其实只需要整数就可以。然后这种酷似整除分块的结构提示我们很多 \(y\) 的取值都是多余的,只需要保留所有是 \(x_i\) 的倍数的取值就做到了不重不漏。

要求 \([1,k]\) 的答案,我们可以先二分出最大的满足 \(\sum\lfloor\frac{y}{x_i}\rfloor\le k\)\(y_{\max}\),然后不超过 \(y_{\max}\) 的是 \(x_i\) 的倍数的数的个数即为答案。

这是一个经典容斥,记 \(X\) 为所有 \(x_i\) 构成的集合,答案即为:

\[\sum\limits_{S\subseteq X}(-1)^{|S|-1}\left\lfloor\frac{y_{\max}}{\operatorname{lcm}S}\right\rfloor \]

需要注意的是 \(\operatorname{lcm}S\) 可能特别巨大,在计算过程中超过 \(y_{\max}\) 了就可以退出了。

容斥复杂度好像写高了,不过也过了,防 hack 就不放代码了。