CF2173C Kanade's Perfect Multiples 题解

Mier_Samuelle · 2025-12-16 22:39:54 · 题解

一个比较显然的结论：序列 A 中的最小数一定在 B 中。否则若要满足条件 1，就必须将比最小数更小的数放入 B 中，而这个更小的数一定无法满足条件 2。

于是我们得到了一个贪心做法：不断将目前 A 中的最小数放入 B 中，然后将 A 中所有最小数的倍数打上标记（不用再选）。重复此过程直到 A 清空。中途每放入一个数，就检查其是否满足条件 2，不满足直接跳出。

时间复杂度似乎很大？但是由于当 a_i 很小 k 很大时，条件 2 很难满足，因此完全可以过。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n, m, k;
set <int> a, b, flag;
void solve(){
    cin >> n >> k;
    flag.clear();
    a.clear();
    b.clear();
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a.insert(x);
        flag.insert(x);
    }
    while (!a.empty()){
        int x = *a.begin();
        b.insert(x);
        for (int y = x; y <= k; y += x){
            if (flag.find(y) == flag.end()){
                cout << "-1" << endl;
                return;
            }
            if (a.find(y) != a.end()){
                a.erase(*a.find(y));
            }
        }
    }
    cout << b.size() << endl;
    for (int x : b){
        cout << x << " ";
    }
    cout << endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::