at_arc122_e Increasing LCMs 题解
_
·
·
题解
神秘构造。
考虑倒序构造，每次在答案开头新增一个数 $x$。
设能作为 $x$ 的 $a_i$ 的集合为 $b$。随着 $a$ 内数的数量减少，$\operatorname{lcm}(a_i)$ 单调不升，因此 $b$ 内的数只会新增不会被移除。
每次任意选取 $b$ 内数放在答案开头即可。
无解当且仅当 $b$ 为空且 $a$ 不为空。由于 $b$ 内数不会被移除，该做法能保证正确性。（以答案的长度作为时刻，不存在某个 $a_i$ 在 $t$ 时刻能作为 $x$，在 $t+\Delta>t$ 时刻不行）
暴力枚举 $x$，时间复杂度 $\mathcal{O}(n^3\log a_i)$。
[提交记录](https://atcoder.jp/contests/arc122/submissions/38664919)。