题解：P17233 [Algo Beat Contest 017 B] 线性筛

Charged_Charge · 2026-08-10 17:42:12 · 题解

思路：

首先，由于 n\le 10^6，并且小于等于 10^6 的完全立方数只有 100 个，所以可以提前预处理出所有满足要求的完全立方数。

接下来就开始删数了。我们把一个完全立方数到下一个完全立方数之间的区间进行划分，并归属于当前完全立方数。注意到一个区间在一次删除操作结束后的下标偏移量恰好等于当前区间的编号。但还有难点，若跨区间，就不能遵循上一个区间的偏移规则，要遵循当前区间的。另外，从上一个区间跨到当前区间的起始位置要是当前区间端点加上上一个区间的编号。

AC 代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
ll n, m, cnt, ans;
ll a[N], b[N], id[N], pl[N], now[N];
vector<ll> pr[N];
int main(){
//    freopen("sj.txt", "r", stdin);
//    freopen("t2.txt", "w", stdout);
    cin >> n;
    m = n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 1; i <= 1000000; i++){
        for(int j = 1; j * j * j <= i; j++){
            if(j * j * j == i){
                b[++cnt] = i;
                id[cnt] = i;
                pl[cnt] = cnt;
                now[cnt] = cnt;
                break;
            }
        }
    }

    while(m){
        ans++;
        ll idx = 0;
        for(int i = 1; i <= cnt; i++){
            if(id[i] > n){
                continue;
            }

            pr[ans].push_back(a[id[i]]);
            id[i] += pl[i];
            idx++;

            if(id[i] >= b[now[i] + 1] && id[i] <= n){
                id[i] = b[now[i] + 1] + i;
                pl[i] = now[i] + 1;
                now[i]++;
            }
        }

        m -= idx;
    }   

    cout << ans << '\n';
    for(int i = 1; i <= ans; i++){
        for(auto p : pr[i]){
            cout << p << ' ';
        }

        cout << '\n';
    }
    return 0;
}