2428: 【普及-】【P1036】选数
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：8
题目描述
已知 个整数 ，以及 个整数 （）。从 个整数中任选 个整数相加，可分别得到一系列的和。例如当 ，， 个整数分别为 时，可得全部的组合与它们的和为：
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：。
输入
第一行两个空格隔开的整数 （，）。
第二行 个整数，分别为 （）。
输出
输出一个整数，表示种类数。
样例输入 复制
4 3
3 7 12 19样例输出 复制
1提示
NOIP 2002 普及组第二题
#include<bits/stdc++.h>
using namespace std;
int a[21];
int n;
bool is_prime(int x) {
for (int i=2;i*i<=x;i++) {
if (x%i==0) return 0;
}
return 1;
}
bool eval(int S) {
int sum=0;
for (int i=0;i<n;i++) {
if (S&(1<<i)) sum+=a[i];
}
return is_prime(sum);
}
int main(){
int k,ans=0;
cin>>n>>k;
for (int i=0;i<n;i++) cin>>a[i];
int U=1<<n;
for (int S=0;S<U;S++) {
if (__builtin_popcount(S)==k && eval(S)) ans++;
}
cout<<ans<<endl;
return 0;
}