广州C++信奥老师解一本通题 1919：【02NOIP普及组】选数
【题目描述】
已知nn个整数x1,x2,……xn 以及一个整数K(K＜n)。从n个整数中任选K个整数相加,可分别 得到一系列的和。例如当n=4, k=3 4个整数分别为3,7,12,19 3, 7,12,19时,可得全部的组合与它们的和为:
3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:(3+7+19=29)。
【输入】
第一行为n和k(1≤n≤20,k＜n)
第二行为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,ans=0;
bool isPrime(long long n)
{
if(n<=1)
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(cnt>k)
{
long long sum=0;
for(int i=1;i<=k;i++)
sum+=path[i];
if( isPrime(sum) )
ans++;
return;
}
for(int i=start;i<=n;i++) //递归尝试数组元素下标 1，2，3，4等
{
path[cnt]=a[i];
dfs(i+1,cnt+1);
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
memset(path,0,sizeof(path));
dfs(1,1);
cout<<ans;
return 0;
}