2477: 【普及-】【P1036】选数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
已知 个整数 ，以及 个整数 （）。从 个整数中任选 个整数相加，可分别得到一系列的和。例如当 ，， 个整数分别为 时，可得全部的组合与它们的和为：
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：。
输入
第一行两个空格隔开的整数 （，）。
第二行 个整数，分别为 （）。
输出
输出一个整数，表示种类数。
样例输入 复制
4 3
3 7 12 19样例输出 复制
1提示
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[25];
long long ans;
bool is_prime(int x){
//0和1特判真的没啥用对这题
for(int i = 2;i * i <= x; i++)
if(x % i == 0)
return false;
return true;
}
void dfs(int m, int sum, int startx){
//m代表现在选择了多少个数
//sum表示当前的和
//startx表示升序排列，以免算重
if(m == k){
if(is_prime(sum))
ans++;
return ;
}
for(int i = startx; i < n; i++)
dfs(m + 1, sum + a[i], i + 1);
//步数要加1,和也要加,升序起始值要变成i+1,以免算重
return ;
}
int main(){
scanf("%d%d",&n,&k);//输入
for(int i = 0; i < n; i++)
scanf("%d",&a[i]);//循环读入
dfs(0,0,0);//调用函数
printf("%d\n",ans);//输出答案
return 0;//结束程序
}