Catalog
洛谷P1036选数

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[1000], book[1000], m,n,sum,ans;
bool isprime(int x) {
if (x == 0 || x == 1) return 0;
else {
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0)
return 0;
}
return 1;
}

void dfs(int x, int y) {
for (int i = y; i <= m; i++) {
if (book[i] == 0) {
book[i] = 1;
sum += a[i];
}
if (n == x) {
if (isprime(sum)) ans++;
}
else
dfs(x + 1, i + 1);
sum -= a[i];
book[i] = 0;
}
}

int main() {

cin >> m >> n;
for (int i = 1; i <= m; i++)
cin >> a[i];
dfs(1, 1);
printf("%d", ans);
return 0;

}
Author: superzhaoyang
Link: http://yoursite.com/2019/09/23/洛谷P1036选数/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Donate
  • 微信
  • 支付宝

Comment