CF1166E The LCMs Must be Large 做题记录

有一个长度为 $n$（$n<=10^4$）的内容未知的序列，再给 $m$（$m<=50$）个限制，每个限制会给一个位置集合 $S$，需要让 $S$ 中所有位置上的数的 $\operatorname{lcm}$ 严格大于序列里剩下的数的 $\operatorname{lcm}$，求是否存在一个这样的序列满足所有限制。存在一个序列输出 possible，否则输出 impossible。

有个结论，这 $m$ 个集合只要两两有交就有解，否则无解。

首先证明不是两两有交就无解，考虑反证。若存在两个集合 $A$ 和 $B$ 无交，则设 $\operatorname{lcm}_{u\in A} a_u=x,\operatorname{lcm}_{u\in B}a_u=y$。那么由于 $A$ 的补集包含 $B$，所以 $A$ 的补集的 $\operatorname{lcm}$ 一定大于等于 $y$，设它为 $z$；同理，$B$ 的补集的 $\operatorname{lcm}$ 一定大于等于 $x$，设它为 $w$。由于 $x>z,z\ge y$，所以 $x>y$；又由于 $y>w,w\ge x$，所以 $y>x$，与 $x>y$ 矛盾，得证。

然后考虑在集合两两有交的情况下构造解，可以考虑如下构造：

1. 把所有 $a_i$ 赋值为 $1$；
2. 给每个集合 $S_i$ 赋一个和别的集合不同的质数 $p_i$，每个满足 $u\in S_i$ 的 $a_u$ 都乘上 $p_i$；

由于集合两两有交，所以一个集合内的 $\operatorname{lcm}$ 都是 $\prod\limits_{i=1}^mp_i$，而集合外面的 $\operatorname{lcm}$ 一定会少一个 $p_i$，比集合里的小。

所以直接 $O(m^2n)$ 就行了。