本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-10 12:31:31

如果质因数数量非常少，比如 $n \le 30$，那么我们就可以直接状压，把质因数是否出现压起来。设 $f(i, S, T)$ 表示前 $i$ 个人，一个选了状态 $j$，另一个选了 $k$ 的方案数。

很难不注意到刷表转移

$$ \begin{aligned} f(i, S \cup K_i, T) \gets f(i, S, T) \iff S\cup K_i \cap T = \arnothing \ f(i, S, T \cup K_i) \gets f(i, S, T) \iff T\cup K_i \cap S = \arnothing \end{aligned} $$

但是问题来了，$n \le 500$，我们连这玩意儿压都压不起来。

很难不注意到，一个数 $x$ 大于 $\sqrt x$ 的质因数最多只有一个。我们要让两个集合所选的质因数交空，实际上就是保证小因子交空的前提下，让大因子不同。

我们可以把每一个数分解，然后按大因子排序，也就是把相同的一段放在了一起。

这个大因子只有三种可能：给 $S$，给 $T$ 和都不给。

设 $g(i, S, T)$ 表示这个大因子不在 $T$ 中的方案数，也就是可以在 $S$ 中的方案数，那么 $g$ 的转移是类似的；同理，我们可以算出可能在 $T$ 中的方案数。

合并解时候，要容斥掉一个 $f(i, S, T)$，因为 $g$ 和 $h$ 都可以表示都不给的情况。

之前想过质因子状压的 idea，但是正是因为会让值域太小而没想到解决方案。这题真的不错。