题目

[NOIP2002 普及组] 选数

题目描述

已知 $n$ 个整数 $x_1,x_2,\cdots ,x_n$以及 $1$ 个整数 $k$$k<n$。从 $n$ 个整数中任选 $k$ 个整数相加可分别得到一系列的和。例如当 $n=4$$k=3$$4$ 个整数分别为 $3,7,12,19$ 时可得全部的组合与它们的和为

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在要求你计算出和为素数共有多少种。

例如上例只有一种的和为素数$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$$1\le n\le 20$$k<n$。

第二行 $n$ 个整数分别为 $x_1,x_2,\cdots ,x_n$$1\le x_i\le 5\times 10^6$。

输出格式

输出一个整数表示种类数。

样例 #1

样例输入 #1

4 3
3 7 12 19

样例输出 #1

1

提示

【题目来源】

NOIP 2002 普及组第二题

解题思路

• 质数判断+dfs。

Code

#include <iostream>
#include <vector>

using namespace std;


int ans = 0;
int k, n, nums[25];

// 首先定义一个判断是否为质数的函数
bool is_prime(int n) {
	vector <bool> tag(n + 1, true);
	tag[0] = tag[1] = false;
	for (int i = 2; i <= n; i++) {
		if (tag[i] && i == n) {
			ans++;
			return true;
		}
		for (int j = i; j * i <= n; j++) {
			tag[i * j] = false;
			if (i * j == n) {
				return false;
			}
		}
	}
}

// 定义dfs函数
void dfs(int start, int sum, int m) {
	if (m == k) {
		is_prime(sum);
	}
	for (int i = start; i < n; i++) {
		dfs(i + 1, sum + nums[i], m + 1);
	}

}


int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	dfs(0, 0, 0);
	cout << ans << endl;
	return 0;
}

运行结果