网站开发工程师专业好不好,智联招聘网站怎么做两份简历,网站建设期末总结,自助搭建平台【题目描述】 已知nn个整数x1,x2,……xn 以及一个整数K(K#xff1c;n)。从n个整数中任选K个整数相加,可分别 得到一系列的和。例如当n4, k3 4个整数分别为3,7,12,19 3, 7,12,19时,可得全部的组合与它们的和为: 371222 371929 7121938 3121934 现在,要求你计算出和为…【题目描述】 已知nn个整数x1,x2,……xn 以及一个整数K(Kn)。从n个整数中任选K个整数相加,可分别 得到一系列的和。例如当n4, k3 4个整数分别为3,7,12,19 3, 7,12,19时,可得全部的组合与它们的和为: 371222 371929 7121938 3121934 现在,要求你计算出和为素数共有多少种。 例如上例,只有一种的和为素数:(371929)。 【输入】 第一行为n和k(1≤n≤20,kn) 第二行为n个数 x1x2……xn(1≤xi≤5000000),各数之间用一个空格隔开) 【输出】 一个整数(满足条件的种数)。 【输入样例】
4 3
3 7 12 19
【输出样例】
1
此题跟1317【例5.2】组合的输出 解法类似 #include bits/stdc.h
using namespace std;
long long path[21],a[21]; //path存放组合的元素的数字
int n,k,ans0;
bool isPrime(long long n)
{if(n1)return false;for(int i 2; i sqrt(n);i)if(n % i 0)return false;return true;
}
void dfs(int start,int cnt)
{if(cntk){long long sum0; for(int i1;ik;i)sumpath[i];if( isPrime(sum) )ans;return;}for(int istart;in;i) //递归尝试数组元素下标 1234等 {path[cnt]a[i];dfs(i1,cnt1);}
}
int main()
{cinnk;for(int i1;in;i)cina[i];memset(path,0,sizeof(path));dfs(1,1);coutans;return 0;
}
