抗击疫情联合训练赛第28场 E Give-a-Gnocchi

题意

一句话题意,就是问不含小于等于n的素数因子的第k大合数。(n,k<=1000)
(样例解释中的189应该是11 * 17=187,在此更正一下,但是不影响做这道题。)

分析

读懂题目之后,不含小于等于n的素数因子,意思就是只含有大于n的素数因子的合数,我们要找第k个。

然后因为没有什么好思路,所以我们先确定一下本题答案的上界,也就是n等于1000,k等于1000的时候,这个数大约在什么范围。

而最小的大于1000的素数因子可以找到是1009,合数最小包含两个素数因子,暂时先假设另一个所含素数因子为p1,因此找到的合数便可以表示成 1009* p1

因为k最大是1000,所以我们暴力的想,p1是大于1000的第1000个素数,此时的p1不过1e4左右,这其实确定出来的合数才大约1e7而已,而实际找到的第k个数要远远小于该合数。至于包含三个以及三个以上素数因子的情况,乘起来最少也要1e9,因此在确定最大数的时候无需考虑。

这时候当我们确定了最大的数也不超过1e7的时候,就可以大胆的暴力做了,打出1e7的素数表,然后用小于n的素数筛一下是否满足题意,暴力找就可以了。复杂度大约是2e6*log。

总结一下,这题就实际上根据数据范围确定最大数的边界,然后得到勇气之后暴力解题。

欧拉筛法不会的同学建议百度自学。
推荐 https://oi-wiki.org/math/sieve/

最后贴一下AC代码。

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
const int N=1e7+5;
const int tmp=31;
const int mod=1e6+7;
const double eps=1e-8;
const double pi=acos(-1);
int p[N/5],cnt;
bool vis[N];
void erla()
{
    int n=N-5;
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&p[j]*i<=n;j++){
            vis[p[j]*i]=1;
            if(i%p[j]==0)break;
        }
    }
}
int main()
{
    erla();
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=n+1;;i++){
        if(!vis[i])continue;
        int f=0;
        for(int j=1;p[j]<=n;j++){
            if(i%p[j]==0){
                f=1;
                break;
            }
        }
        if(!f)k--;
        if(k==0){
            printf("%d\n",i);
            return 0;
        }
    }

    return 0;
}