CF1166E The LCMs Must be Large 做题记录

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

有个结论,这 mm 个集合只要两两有交就有解,否则无解。

首先证明不是两两有交就无解,考虑反证。若存在两个集合 AABB 无交,则设 lcmuAau=x,lcmuBau=y\operatorname{lcm}_{u\in A} a_u=x,\operatorname{lcm}_{u\in B}a_u=y。那么由于 AA 的补集包含 BB,所以 AA 的补集的 lcm\operatorname{lcm} 一定大于等于 yy,设它为 zz;同理,BB 的补集的 lcm\operatorname{lcm} 一定大于等于 xx,设它为 ww。由于 x>z,zyx>z,z\ge y,所以 x>yx>y;又由于 y>w,wxy>w,w\ge x,所以 y>xy>x,与 x>yx>y 矛盾,得证。

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

  1. 把所有 aia_i 赋值为 11
  2. 给每个集合 SiS_i 赋一个和别的集合不同的质数 pip_i,每个满足 uSiu\in S_iaua_u 都乘上 pip_i

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

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