「解题报告」ARC122E Increasing LCMs

紫题不会了，感觉要退役了

前缀 \(\mathrm{lcm}\) 的限制很强，考虑每次消去一个数。

发现最后一个数没有依赖，考虑最后一个数的条件，其实就是最后一个数不是前 \(n-1\) 个数的 \(\mathrm{lcm}\) 的倍数，即 \(\displaystyle \gcd(\mathop{\mathrm{lcm}}_ {i\ne j}(a_j),a_i) < a_i\)。这个条件可以改写为 \(\displaystyle \mathop{\mathrm{lcm}}_ {i\ne j}(\gcd(a_i, a_j)) < a_i\)，这便将 \(a_i\) 与前 \(n-1\) 个数的限制拆开了。我们只需要找到满足条件的 \(a_i\)，然后将最后一个数删去，就可以递归子问题了。

发现每删除一个数后，\(\mathrm{lcm}\) 不会增加，那么合法的 \(a_i\) 的集合不会减小，所以可以任意选取 \(a_i\)。如果某一时刻没有合法的 \(a_i\) 了，那么说明无解。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n;
long long a[MAXN];
bool vis[MAXN];
__int128_t lcm(__int128_t a, __int128_t b) {
    return a / __gcd(a, b) * b;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    vector<long long> ans;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= n; j++) if (!vis[j]) {
            __int128_t l = 1;
            for (int k = 1; k <= n; k++) if (!vis[k] && k != j)
                l = min((__int128_t) a[j], lcm(l, __gcd(a[j], a[k])));
            if (l < a[j]) {
                vis[j] = 1;
                ans.push_back(a[j]);
                break;
            }
        }
        if (ans.size() != i) {
            printf("No\n");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        ans.push_back(a[i]);
    }
    reverse(ans.begin(), ans.end());
    printf("Yes\n");
    for (long long i : ans) {
        printf("%lld ", i);
    }
    printf("\n");
    return 0;
}