CF1333F Kate and imperfection 题解 线性筛

题目链接：http://codeforces.com/problemset/problem/1333/F

题目大意：

kate有一个集合S，S中的元素是1到n的整数

她认为集合S的一个子集M的集合的不完美值等于
\(\max_{a,b\in M} gcd(a,b)\) 且\(a!=b\)

对于整数k从2到n，kate想要知道所有大小为k的S的子集中，不完美值最小是多少

解题思路：

• 最先找的是素数，对应 \(1\)；
• 然后会找 \(4\)，对应 \(2\)；
• 然后会找 \(6, 9\)，对应 \(3\)；
• 然后会找 \(8\)，对应 \(4\)；
• 然后会找 \(10, 15, 25\)，对应 \(5\)，
• ……

每加入一个数字，对应的 gcd 对应的就是它的最大的那个（非本身）的因数（素数比较特殊，就是 \(1\)）

发现可以用线性筛预处理一下，求出每个整数最大的那个非本身的因数。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
bool isp[maxn];
int prime[maxn], cnt, fac[maxn], t[maxn];

void init(int n) {
    fac[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!fac[i])
            prime[cnt++] = i, fac[i] = 1;
        for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
            fac[i * prime[j]] = i;
            if (i % prime[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= n; i++)
        t[fac[i]]++;
}

int n, p, tot;

int main() {
    cin >> n;
    init(n);
    for (int k = 2; k <= n; k++) {
        while (tot < k)
            tot += t[++p];
        cout << p << " ";
    }
    return 0;
}