标签：ARC122E Increasing 数列 gcd 末尾 lcm operatorname LCMs

[ARC122E] Increasing LCMs

Atcoder：[ARC122E] Increasing LCMs

洛谷：[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\)，可以进行如下转化：

\[\begin{aligned} & \gcd(a_i, \operatorname{lcm}(a_j)) = \operatorname{lcm}(\gcd(a_i, a_j)) \end{aligned} \]

这就是容易判断的了。

以下是对上述策略的补充说明。

如果数列 \(\{ 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\) 个数构成的数列也是合法的。

如果原数列是非法的，由于我们的构造是合理的，完全遵循题目要求的规则，因此不可能找到一个合法的数列。

以上。

code ARC122E

标签：ARC122E,Increasing,数列,gcd,末尾,lcm,operatorname,LCMs
From： https://www.cnblogs.com/Schucking-Sattin/p/17705375.html