AcWing 5491. 选数
原题链接
简单
作者:
代码人生
,
2024-02-12 12:44:40
,
所有人可见
,
阅读 75
本题为递归实现组合型枚举的同类题,最后加一个判断质数即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 15;
int n,m;
int x[N];
int ans;
vector<int> v;
bool check(int x){
if(x < 2) return false;
for(int i=2;i<=x/i;i++){
if(x % i == 0){
return false;
}
}
return true;
}
void dfs(int step){
if(v.size() > m || v.size() + (n - step + 1) < m) return ;
if(step == n + 1){
int sum = 0;
for(auto t:v) sum += t;
ans += check(sum);
return ;
}
v.push_back(x[step]);
dfs(step + 1);
v.pop_back();
dfs(step + 1);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d",&x[i]);
dfs(1);
printf("%d",ans);
return 0;
}