题解 ARC122E【Increasing LCMs】

0x3F · 2024-04-12 20:01:28 · 题解

注意到如果一个序列合法，那么其子序列必然合法。

若一个元素 A_i 可以放在末尾，那么必然满足 \operatorname{lcm}(A_1,\cdots,A_{i-1},A_{i+1},\cdots,A_n)\ne\operatorname{lcm}(A_1,\cdots,A_n)。

此时，若其他元素可以构成合法的序列，那么将 A_i 放在末尾即可得到合法的原序列。反之若原序列合法，那么无论 A_i 放在哪里，将其删去以后得到的子序列仍然合法。

因此将 A_i 放在末尾不影响答案。删去 A_i 后，剩下的 A^{\prime}_{1\sim n-1} 继续计算，直到长为 0 则合法，或找不到这样的 A_i 则不合法。

但是上式的值太大了，无法直接计算。考虑转化为 \operatorname{lcm}\left[\gcd(A_1,A_i),\cdots,\gcd(A_{i-1},A_i),\gcd(A_{i+1},A_i),\cdots,\gcd(A_n,A_i)\right]\ne A_i，左式的值不会超过 A_i，可以直接计算。

时间复杂度为 \mathcal{O}(n^3\log V)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
int n;
long long a[110];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    bool flg = true;
    for (int k = n; k >= 1; k--) {
        bool ok = false;
        for (int i = 1; i <= k; i++) {
            long long num = 1LL;
            for (int j = 1; j <= k; j++) {
                if (j != i) {
                    long long tmp = __gcd(a[i], a[j]);
                    num *= tmp / __gcd(tmp, num);
                }
            }
            if (num != a[i]) {
                swap(a[i], a[k]);
                ok = true;
                break;
            }
        }
        if (!ok) {
            flg = false;
            break;
        }
    }
    if (flg) {
        cout << "Yes" << endl;
        for (int i = 1; i <= n; i++) {
            cout << a[i];
            if (i != n) cout << ' ';
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}