[SCOI2010] 幸运数字
发布时间：2025-09-23 点击量：67
看过 \(\rm{TJ}\) 了, 讲真有点匆忙, 虽然说是讲过的题
首先转化题意, 规定由 \(6, 8\) 组成的数字是 "幸运数字" , 求 \([A, B]\) 中, 幸运数字的倍数的个数
容易发现 "幸运数字" 是好算的, 打表或者记忆化搜索都行
考虑怎么计算一个集合中数的倍数个数
联想到之前一道题, 考虑容斥原理去做, 这个题还不太需要筛子
具体怎么容斥原理?
你注意到我们这个题可以用差分的想法去做, 只需要考虑 \([0, x]\) 区间中的幸运数字的倍数的个数
枚举集合, 可以知道
\[f(x)=\sum_{s=1}^{2^m - 1} (-1)^{\lvert s \rvert - 1} \left \lfloor\frac{x}{\mathop{lcm}(a_1, a_2, \cdots, a_{\lvert s \rvert})} \right \rfloor
\]
这样直接做是 \(2^{2046}\) 的, 啊?
怎么优化
考虑 \(3\) 个剪枝:
- 发现对于两个幸运号码 \(a,b\) , 如果 \(a \mid b\) , 那么对于所有的 \(b \mid x\) 就一定有 \(a \mid x\) , 因此这样的 \(b\) 是不必要的, 去掉所有这样的 \(b\) 后, 还剩下 \(943\) 个幸运号码
- 当前的 \(\mathop{lcm}\) 一旦大于 \(B\) 就不再继续搜索, 这样复杂度就能大大降低
- 将预处理出的幸运号码从大到小排序, 使 \(\mathop{lcm}\) 能更快地超越上界 \(B\)
考虑容斥怎么写, 观察到可以用搜索的方式方便剪枝
一类: 先找到一个集合, 再求这个集合中的数的倍数的问题, 使用容斥原理方便解决
很大的算法也可以考虑剪枝
容斥是可以用搜索解决的
讲真这个题最难的部分是优化到 \(2^{946}\) 之后还有信心能过的
