[ARC122E] Increasing LCMs
Atcoder：[ARC122E] Increasing LCMs
Solution
应该意识到这题的核心思想在于构造，想办法将原问题不断划分为子问题。
此题策略的证明不算太难，但以我目前的水平肯定不可能靠严密的证明做出这道题。
猜，直接把满足条件的数放在末尾，将大小为 \(n\) 的问题划归到大小为 \(n - 1\) 的问题。如果找不到合适的末尾，就输出无解。
对于判断是否能放到末尾，直接求 \(\operatorname{lcm}(a_j)\) 是麻烦的。
把整除的条件写成 \(\gcd(a_i, \operatorname{lcm}(a_j)) < a_i\)，即强行套上一个 \(\gcd\)。
考虑利用唯一分解定理，\(\gcd\) 对应次数求 \(\min\)，\(\operatorname{lcm}\) 对应次数求 \(\max\)，可以进行如下转化：
这就是容易判断的了。
以下是对上述策略的补充说明。
如果数列 \(\{ a_i \}\) 是合法的，并且存在一个元素 \(x = a_p\) 能够放到 \(a\) 数列的末尾，则将 \(x\) 放到末尾后，新数列仍然合法。
对于 \(1 \sim p - 1\) 的数，没有影响。对于 \(p + 1 \sim n\) 的数，\(\operatorname{lcm}(a_j)\) 砍掉了一个 \(x\)，因此 \(\gcd(a_i, \operatorname{lcm}(a_j))\) 值不增，这些数仍然合法。
又因为我们钦定了 \(x\) 是能够放到末尾的，所以新数列中的所有位置都是合法的。
假设当前能放到末尾的元素集合为 \(b\)，则任取 \(b\) 中的元素放到末尾，均不会影响合法序列的可行性。
根据上一条，如果原数列是合法的，把 \(a_p\) 放到末尾后，剩下的 \(p - 1\) 个数构成的数列也是合法的。
如果原数列是非法的，由于我们的构造是合理的，完全遵循题目要求的规则，因此不可能找到一个合法的数列。
以上。