[NOIP2002 Popular Group] Options
Title Link
Title Description
known (science)\(n\) integer (math.)\(x_1,x_2,\cdots,x_n\)as well as\(1\) integer (math.)\(k\)（\(k<n\)). From\(n\) any one of a number of integers\(k\) A series of sums can be obtained by adding a series of integers separately. For example, when\(n=4\)，\(k=3\)，\(4\) The integers are respectively\(3,7,12,19\) When, it is obtained that all the combinations with their sums are:
\(3+7+12=22\)
\(3+7+19=29\)
\(7+12+19=38\)
\(3+12+19=34\)
Now, you are asked to calculate the total number of ways in which the sum is prime.
For example, in the above example, the sum of only one kind is prime:\(3+7+19=29\)。
input format
Integers separated by two spaces in the first line\(n,k\)（\(1 \le n \le 20\)，\(k<n\)）。
second line\(n\) integers, which are\(x_1,x_2,\cdots,x_n\)（\(1 \le x_i \le 5\times 10^6\)）。
output format
Outputs an integer representing the number of species.
Sample #1
Sample Input #1
4 3
3 7 12 19
Sample Output #1
1
draw attention to sth.
[Title source]
NOIP 2002 Popular Group Question 2
#include<vector>
#include<iostream>
using namespace std;
int n, k;
int a[25];
vector<int> path;
int cnt;
int isprime(int n) {
if (n <= 1) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
for (int i = 3; i <= n / i; i+=2) {
if (n % i == 0) return 0;
}
return 1;
}
void dfs(int n, int k, int sum, int a[],vector<int> path,int startindex) {
if (() == k) {
if (isprime(sum)) cnt++;
return;
}
//Remember to pass in1
for (int i = startindex; i <= n-(())+1; i++) {
sum += a[i];
path.push_back(a[i]);
dfs(n, k, sum, a, path, i + 1);
sum -= a[i];
path.pop_back();
}
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(n, k, 0, a, path, 1);
cout << cnt;
return 0;
}