Codeforces Round #632 (Div. 2) F. Kate and imperfection 埃筛 gcd

https://codeforces.com/contest/1333/problem/F

给定一个有n个数的集合S={1,2,3,...,n}.

集合M⊆S，M中的数两两组合，最大的gcd(a,b)，被定义为不完美的值 I_m。

现在有一个 k∈{2,…,n}，在S里面找到 k 个数，使得 I_k最小，求 $I_{2}$ $I_{2}$

$I_{2}$

思路：gcd的最大值要最小，质数的gcd都为1，肯定是最小的，那么当k小于等于 [1,n]中质数的个数时，I_k=1，然后把非质数的最大约数的最小值依次选入集合中，那么这个数的最大约数就是这个集合的最大gcd。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const int mod=1e9+7;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;

int a[MAXN];//记录每个数的最大约数，质数为1
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)a[i]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=i+i;j<=n;j+=i)
        {
            a[j]=i;
        }
    }
    sort(a+2,a+1+n);
    for(int i=2;i<=n;i++)printf("%d%c",a[i],i==n?'
':' ');
    return 0;
}

View Code