P9489 ZHY的表示法
smqa
·
·
题解
题目
首先发现是求 [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！仙品！金婚！纯爱！爽！
（为了说题外话我写了一整篇题解，管理员大大求过）