AcWing 5491. 选数
原题链接
简单
作者:
zy4466
,
2024-04-08 20:00:01
,
所有人可见
,
阅读 4
#include <iostream>
using namespace std;
const int N = 30;
int p[N], g[N];
bool st[N];
int n, k;
int cnt;
bool pan(int x)//判断素数
{
for(int i = 2; i * i <= x; i ++ )
if(x % i == 0)
return false;
return true;
}
void dfs(int u, int start)
{
if(u > k)//当数大于k时,这一层递归结束
{
int count = 0;
for(int i = 1; i <= k; i ++ )
{
// cout << p[i] << " ";
count += p[i];
}
// cout << endl;
if(pan(count))//记得是在循环外进行判断
cnt ++;
return;
}
for(int i = start; i <= n; i ++ )
{
if(!st[i])
{
p[u] = g[i];
st[i] = true;
dfs(u + 1, i + 1);//第u个点已经确定,继续第u + 1个点
st[i] = false;//返回初始状态
}
}
}
int main(){
cin >> n >> k;
for(int i = 1; i <= n; i ++ )
{
cin >> g[i];
}
dfs(1, 1);
cout << cnt << endl;
return 0;
}