E - Increasing LCMs Editorial by evima


\(A_i\) can be at the end of \(x\) if and only if \(\operatorname{GCD}(\operatorname{LCM}_{j \neq i}(A_j),A_i) < A_i\), which we can rewrite to \(\operatorname{LCM}_{j \neq i}(\operatorname{GCD}(A_j,A_i)) < A_i\).

If there is no such \(A_i\), the answer is No. Otherwise, it turns out that we can arbitrarily choose one such \(A_i\) and make it the last element of \(x\). We can see this from the following fact: if a solution exists, any solution will still be valid after moving \(A_i\) that satisfies the above condition to the end. Therefore, we can fix the elements of \(x\) one by one from the end.

A naive implementation of this approach will still take just \(O(N^3\log (\max(A_i)))\) time, which is fast enough.

posted:
last update: