广州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;
}