容易想到将所求差分,变为 \([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 就不放代码了。
标签:P9489,ZHY,题解,rfloor,答案,max From: https://www.cnblogs.com/ruierqwq/p/LG-P9489.html