[SNOI2017] 遗失的答案 - 洛谷P5366
给定 \(n, g, l\) 以及 \(T\) 组询问，每组询问给定 \(x\)，问有多少个集合非空 \(S\) 包含 \(x\) 且 \(S \subseteq \{1, 2 \dots n \}\) 且 \(S\) 内元素的最大公约数为 \(g\)，最小公倍数为 \(l\)。
\(1 \le n, g, l, x \le 10^8, T \le 10^5\)
标签
质因数分解，状压 DP，分治先判掉一些极端情况，\(g \nmid l, x \nmid l, g \nmid x\)，这些情况答案都是 \(0\)。
考虑把包含 \(x\) 这个条件去掉（简化问题），有多少个 \(S\)？
其实 \(g\) 没什么用，将 \(n, l, x\) 都除以 \(g\) 即可，并且 \(S\) 内的元素必须是 \(l\) 的因数（最多 \(800\)，设为 \(d\) 个）。然后考虑将 \(l\) 质因数分解：\(l = p_1^{k_1}p_2^{k_2} \cdots p_m^{k_m}\)。只需要对于每个 \(1 \le i \le m\)， \(S\) 内的元素有至少一个 \(p_i\) 的指数为 \(k_i\)，有至少一个为 \(0\) 即可。
因为 \(l\) 最多只有 \(8\) 个质因子（\(2 \times 3 \times 5 \times \cdots \times 23 = 223092870 > 10^8\)），可以考虑状压。设 \(l\) 有 \(c\) 个质因子，每个数对应一个 \(4^c\) 的状态，表示对于 \(p_i\) 的指数是否为 \(k_i/0\)。然后进行一个 \(4^cd\) 的状压 DP 即可。
接下来考虑不包括 \(x\) 这个条件。一个十分粗暴的方式是对于前后缀各做一次，然后进行合并，时间复杂度 \(O(6^cd)\)，不知道能否通过。
这里介绍一种不需要高级算法的做法：分治（诶，被分治创飞的战绩又添一笔）
先考虑容斥，用总方案减去不包含 \(x\) 的方案。分治到左边的时候，把右边的数加进来；分治到右边的时候，把左边的数加进来。这样递归到叶子的时候，就把所有不是 \(x\) 的都加进来了。
时间复杂度：\(O(4^cd \log d)\)。被 FWT 之类的神秘做法杀爆了。
因为 \(c, d\) 很难同时取满，而且有状态跑不到（对于一个数 \(p_i\) 的指数不可能同时等于 \(k_i, 0\)），跑的还是挺快的。
总结以下，这个题从简单问题入手，先去掉一个条件，搞出一个状压的做法。加入那个棘手条件后使用容斥 + 分治的做法快速进行计算，减少不必要的合并。