[CodeForces1176D] Recover it!（思维，数论）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://codeforces.com/contest/1176/problem/D

题意：给你一个$2n$个数的数组$b$，要你求$a$，其中$a$是生成$b$数组的数组。给出生成$b$的规律：

  1. 如果$a_i$是素数，那么$b$中会有素数表中第$a_i$个素数。
  2. 如果$a_i$是合数，那么$b$中会有这个数本身以及$a_i$最大的非自己的因数。

要求输出这个$a$数组。

这个题很有意思，我们先考虑如果$a_i$是素数，那么输出的就是第$a_i$个素数，于是我们首先想到的当然是打一个素数表。

再考虑$a_i$是合数的情况，除了输出自己以外还要输出最大的因数。数据规模太大，不过我们注意到：设$x$是$a_i$最小的因数，$y$是最大的因数，那么$a_i=xy$，于是我们还需要额外记录每一个数的最小因数，这样是可以线性筛的。

于是输入$b$数组，统计每个数字出现的次数，按照合数和质数分别依次输出结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
 
using namespace std;
using LL = long long;

const int maxn = 3000010;
int n, b;
int pre[maxn], vis[maxn];
vector<int> prime;

void init() {
  memset(pre, 0, sizeof pre);
  prime.clear();
  for (int i = 2; i < maxn; i++) {
    if (pre[i] == 0) {
      pre[i] = i;
      prime.emplace_back(i);
    }
    for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) {
      if (prime[j] > pre[i]) break;
      pre[i * prime[j]] = prime[j];
    }
  }
}

signed main() {
  // freopen("in", "r", stdin);
  init();
  while (cin >> n) {
    memset(vis, 0, sizeof vis);
    for (int i = 1; i <= 2 * n; i++) {
      scanf("%d", &b);
      vis[b]++;
    }
    for (int i = maxn - 1; i > 1; i--) {
      if (pre[i] == i) continue;
      while (vis[i] > 0) {
        printf("%d ", i);
        vis[i]--;
        vis[i / pre[i]]--;
      }
    }
    for (int i = 2; i < maxn; i++) {
      while (vis[i] > 0) {
        printf("%d ", i);
        vis[i]--;
        vis[prime[i - 1]]--;
      }
    }
    printf("\n");
  }
  return 0;
}