U388010 题解

洛谷 U388010 题解

link：https://www.luogu.com.cn/problem/U388010

Sol

首先，我们看到这一条件：

对于每一个 \(1 \le i \le n\)，\(1 \le j \le n\)，\(i \neq j\) 满足 \(a_i \bmod a_j \neq 0,\ a_j \bmod a_i \neq 0\)。

我们知道，质数的因数只有 \(1\) 和本身，所以当序列里全是质数时，一定可以满足这一条件。

那答案是不是第 \(1 \sim n\) 个质数呢？我们继续推理。

题目中说了，\(a_i \bmod 2 \neq 0\)，而偶质数只有 \(2\) 一个。

所以答案是不是从 \(3\) 开始的 \(n\) 个质数？是的，因为题目中说了字典序最小，\(n\) 个数能满足于每一个 \(1 \le i \le n\)，\(1 \le j \le n\)，\(i \neq j\) 满足 \(a_i \bmod a_j \neq 0,\ a_j \bmod a_i \neq 0\) 字典序最小的就是质数。因为可能 \(n < 8\) 时有字典序更小的序列。如 \(n = 2\)，\(a = [3, 4]\)。但是题目保证 \(n \ge 8\)，可以证明 \(n \ge 8\) 时字典序最小的序列就是从 \(3\) 开始的 \(n\) 个质数。

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

using ll = long long;

const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;

bool P(int x) { // 质数筛，时间复杂度 O(sqrt(n))
  if (x < 2) {
    return 0;
  }
  for (int i = 2; i * i <= x; ++ i) { // 枚举 x 的因数
    if (!(x % i)) {
      return 0;
    }
  }
  return 1;
}

int main() {
  int n, cnt = 0; // cnt 统计输出了多少个质数
  cin >> n;
  for (int i = 3; cnt < n; ++ i) {
    if (P(i)) {
      cout << i << ' ';
      ++ cnt;
    }
  }
  cout << '\n';
  return 0;
}