有一个长度为 n(n<=104)的内容未知的序列,再给 m(m<=50)个限制,每个限制会给一个位置集合 S,需要让 S 中所有位置上的数的 lcm 严格大于序列里剩下的数的 lcm,求是否存在一个这样的序列满足所有限制。存在一个序列输出 possible
,否则输出 impossible
。
有个结论,这 m 个集合只要两两有交就有解,否则无解。
首先证明不是两两有交就无解,考虑反证。若存在两个集合 A 和 B 无交,则设 lcmu∈Aau=x,lcmu∈Bau=y。那么由于 A 的补集包含 B,所以 A 的补集的 lcm 一定大于等于 y,设它为 z;同理,B 的补集的 lcm 一定大于等于 x,设它为 w。由于 x>z,z≥y,所以 x>y;又由于 y>w,w≥x,所以 y>x,与 x>y 矛盾,得证。
然后考虑在集合两两有交的情况下构造解,可以考虑如下构造:
- 把所有 ai 赋值为 1;
- 给每个集合 Si 赋一个和别的集合不同的质数 pi,每个满足 u∈Si 的 au 都乘上 pi;
由于集合两两有交,所以一个集合内的 lcm 都是 i=1∏mpi,而集合外面的 lcm 一定会少一个 pi,比集合里的小。
所以直接 O(m2n) 就行了。