Codeforces题解｜1176D - Recover it!

题目信息 📚

【题目描述】

Authors guessed an array $a$ consisting of $n$ integers; each integer is not less than $2$ and not greater than $2 \cdot 10^5$. You don’t know the array $a$, but you know the array $b$ which is formed from it with the following sequence of operations:

Firstly, let the array $b$ be equal to the array $a$;
Secondly, for each $i$ from $1$ to $n$:
- if $a_i$ is a prime number, then one integer $p_{a_i}$ is appended to array $b$, where $p$ is an infinite sequence of prime numbers ($2, 3, 5, \dots$);
- otherwise (if $a_i$ is not a prime number), the greatest divisor of $a_i$ which is not equal to $a_i$ is appended to $b$;
Then the obtained array of length $2n$ is shuffled and given to you in the input.

Here $p_{a_i}$ means the $a_i$-th prime number. The first prime $p_1 = 2$, the second one is $p_2 = 3$, and so on.

Your task is to recover any suitable array $a$ that forms the given array $b$. It is guaranteed that the answer exists (so the array $b$ is obtained from some suitable array $a$). If there are multiple answers, you can print any.

【输入】

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.

The second line of the input contains $2n$ integers $b_1, b_2, \dots, b_{2n}$ ($2 \le b_i \le 2750131$), where $b_i$ is the $i$-th element of $b$. $2750131$ is the $199999$-th prime number.

【输出】

In the only line of the output print $n$ integers $a_1, a_2, \dots, a_n$ ($2 \le a_i \le 2 \cdot 10^5$) in any order — the array $a$ from which the array $b$ can be obtained using the sequence of moves given in the problem statement. If there are multiple answers, you can print any.

【输入样例1】

3
3 5 2 3 2 4

【输出样例1】

3 4 2

【输入样例2】

1
2750131 199999

【输出样例2】

【输入样例3】

1
3 6

【输出样例3】

【题目来源】

https://codeforces.com/problemset/problem/1176/D

题目解析 🍉

【题目分析】

线性筛 + 求最大因子 + 桶思想计数

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;  // a数组最大个数
const int P = 3e6 + 10;  // 最大质数的范围
int book[P]; // 线性筛标记数组
vector<int> p; // 存储1～P所有的质数
int prime[P];  // prime[i]表示质数i对应的下标，如prime[2]=1,prime[5]=3
LL divisor[P];  // div[i]存储i的最大divisor

int n, b[N * 2];  // 读入b数组
int br[P];  // 桶数组，标记b数组中每个数出现几次
vector<int> a; // 存储原数组

// 线性筛，在O(N)的时间内筛选出1~N的质数，存入vector p中
// 在线性筛的基础上，求出P以内每个数的最大divisor（质数为1，合数为自身/最大质因子）
void sieve() {
    for (int i = 2; i < P; i++) {
        if (book[i] == 0) {
            // 当前i为质数
            p.push_back(i);  // 加入p中
            divisor[i] = 1;  // 质数的最大divisor为1
        } else {
            // 当前i为合数，统计其最大质因子
            // 思考为什么这一步不集成在线性筛中
            for (int j = 2; j <= i / j; j++) {
                if (i % j == 0) {
                    divisor[i] = i / j;
                    break;
                }
            }
        }
        // 线性筛
        for (int j = 0; j < p.size() && i * p[j] < P; j++) {
            book[i * p[j]] = 1;
            if (i % p[j] == 0) {
                break;
            }
        }
    }
    // 计算prime数组
    for (int i = 0; i < p.size(); i++) {
        prime[p[i]] = i + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入b数组，并标记
    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> b[i];
        br[b[i]]++;
    }

    // 线性筛预处理
    sieve();

    // 对b数组进行排序
    sort(b + 1, b + 2 * n + 1);

    // 从大到小，逐个处理
    for (int i = 2 * n; i > 0; i--) {
//        cout << b[i] << "   ";
        if (divisor[b[i]] > 1 && br[b[i]] && br[divisor[b[i]]]) {
            // 当前数字为合数
            br[b[i]]--;
            br[divisor[b[i]]]--;
            a.push_back(b[i]);
        } else if (divisor[b[i]] == 1 && br[b[i]] && br[prime[b[i]]]) {
            // 当前数字为质数
            br[b[i]]--;
            br[prime[b[i]]]--;
            a.push_back(prime[b[i]]);
        }
    }

    // 输出a数组
    for (int i = 0; i < a.size(); i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}