[COCI 2008/2009 #2] RESETO

GitHub跳转原题关系图返回列表

按埃氏筛的实际删数顺序模拟，统计第 k 次真正删除的整数。

OJ: luogu

题目 ID: P6421

难度:普及-

标签:模拟数学

日期: 2026-06-18 20:56

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

按题目给定的埃拉托色尼筛法删除 2..n 中的数，要求输出第 k 个被删除的整数。

思路

先看一个可以直接验证想法的朴素解：

每一轮先找到当前最小的未删数 p，再删掉 p 及其所有还没删掉的倍数。

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> alive(n + 1, 1);
    alive[0] = alive[1] = 0;

    int cnt = 0;
    while (true) {
        int p = 0;
        for (int i = 2; i <= n; i++) {
            if (alive[i]) {
                p = i;
                break;
            }
        }

        for (int x = p; x <= n; x += p) {
            if (!alive[x]) continue;
            alive[x] = 0;
            cnt++;
            if (cnt == k) {
                cout << x << '\n';
                return 0;
            }
        }
    }

    return 0;
}

对本题来说，直接模拟已经足够。 实现时可以把外层写成 p = 2..n 顺序扫描：

  • 如果 p 已经被删掉，就跳过；
  • 如果还没删掉，就按步长 p 枚举倍数并删数。

每当真正删掉一个新数，就把计数加一；当计数达到 k 时，这个数就是答案。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> removed(n + 1, 0);
    int cnt = 0;

    for (int p = 2; p <= n; p++) {
        if (removed[p]) continue;
        for (int x = p; x <= n; x += p) {
            if (removed[x]) continue;
            removed[x] = 1;
            cnt++;
            if (cnt == k) {
                cout << x << '\n';
                return 0;
            }
        }
    }

    return 0;
}

复杂度

本题规模很小，直接模拟完全足够。 空间复杂度是 O(n)O(n)。

总结

这题的关键不是求素数，而是严格按照筛法的“删数顺序”去模拟。