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