题解：P1036 [NOIP 2002 普及组] 选数

· · 题解

题目大意：

从 n 个数中选出 k 个数，要选出的数的总和为素数，问共有多少种选法。

思路：

我们可以用递归的方法，先用欧拉筛筛出范围内所有的素数，然后开始递归。递归函数总共有三个参数，用 x 表示决定选的数的下标，用 sum 表示现在选出的数的总值，用 num 表示已经选的数的个数。当 num=k 时，如果 sum 的值为素数，那么最终答案 s \gets s+1，否则 s 不变，然后返回。如果 num<k，那么我们就从 x+1 开始，一直到 n 去枚举、递归。最后输出最终答案 s 即可。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int s,n,k,a[30],f[100000010],b[100000010];//s表示最终答案，a[i]表示第i个可选的数，f[i]表示i是否为素数，b[i]表示范围内第i小的素数 
void dfs(int x,int sum,int num){//x表示决定选的数的下标，sum表示现在选出的数的总值，num表示已经选的数的个数 
    if(num==k){//现在已经选了k个数 
        s+=1-f[sum];//当sum的值为素数时，答案加1，否则加0 
        return;//不用继续选下去了，返回 
    }
    for(int i=x+1;i<=n;i++){//还没有选出k个数，继续选下去 
        dfs(i,sum+a[i],num+1);//递归，从第i个数继续选下去，sum加上a[i]的值，num加1 
    }
    return;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    f[1]=1;//1不是素数 
    int bi=0;//素数数量 
    for(int i=2;i*i<=100000000;i++){//筛出范围内的所有素数 
        if(f[i]==0) b[++bi]=i;//存储新的素数 
        for(int j=1;j<=bi&&i*b[j]<=sqrt(100000000);j++){
            f[i*b[j]]=1;//i*b[j]的值不是素数 
            if(i%b[j]==0) break;//当i为b[j]的整倍数时，退出循环 
        }
    }
    dfs(0,0,0);//开始递归 
    cout<<s;//输出最终答案 
    return 0;
}