【代码超详解】CometOJ C0169 [2002普及组-B]选数

一、题目描述

二、算法分析说明与代码编写指导

先用 https://blog.csdn.net/COFACTOR/article/details/102219189 中的模板打一个质数表，方便快速判断一个数是否为质数。
本题数据较水，直接用 2 到 根号n 一个一个验证是否为 n 的因数来判定 n 是否为质数比先打一个较大的表用于验证来得更快。但是当数据量较大时，常量打表的优势就显现出来了。
本题要求从 n 个数中选 k 个数，枚举这 k 个数的全部组合，判断其和是否为质数。从 n 个数中选 k 个数的排列或组合，这类问题用递归解决是比较方便的。
本题中，enumerate 函数的参数 p 和 q 分别代表可能可选的第一个数和已经选择的数的数量。用 bitset<21> selected 来标记 x1 到 x20 是否已经选过。
p 和 q 的初值分别为 1、0 。
首先设置递归的终止条件，当 q = k 时，将累加的和 s 验证是否为质数。如果是，答案 +1 。
如果不是，就需要继续选数，直到选满。选数的时候，selected 中的对应位置要记为 1 ，然后把这个数累加到 s 中。从深层函数返回时，要从 s 中扣掉这部分，然后把 selected 的对应位重新记为 0 ，为后续的枚举做准备。
每一层函数对应的可选范围为 xp 到 xn 。
举个例：
从数 1、3、5、7、9 中选 3 个，我们列出全部结果来理解这个规律：
1 3 5 、1 3 7 、1 3 9 、1 5 7 、1 5 9 、1 7 9 、3 5 7 、3 5 9 、3 7 9 、5 7 9
可见第一个数有 1 3 5 7 9 可选，当然不会列出 7 和 9 开头的组合。因为第一个数选了 7 时，第二个数只能是选 9 ，第三个数开始 p > n ，循环根本就无法进入，这一层递归就结束了。
第二个数只从 3 5 7 9 一个一个尝试选择就可以试完全部可能的组合。当然第二个数不会是 9 ，不然选第三个数的时候 p > n ，直接结束循环然后就跑到了函数末尾，这一层函数也结束了。
第三个数则是从 5 7 9 中选出的。
比如如果我们选了 1 5 7 并验证了和 s = 13 为质数，第三层函数返回的时候，就要令 selected[4] = 0 ，s -= x[4] ，然后循环执行到 i = 5 ，然后 selected[5] = 1 ，s += 9 ，……
思路想好以后，就可以把代码写出来了。

三、AC 代码

（3 ms）

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#pragma warning(disable:4996)
using namespace std;
const unsigned qty_of_prime = 6543;
unsigned prime[qty_of_prime] = { 2, 3 }, n, k, c = 0, s = 0, x[21]; bitset<21> selected;
inline void genprime() {
	unsigned a = 4, t; bool flag = true;
	for (unsigned i = 2; i < qty_of_prime;) {
		t = sqrt(a), flag = true;
		for (unsigned j = 0; prime[j] <= t; ++j) {
			if (a % prime[j] == 0) { flag = false; break; }
		}
		if (flag) { prime[i] = a, ++i; }
		++a;
	}
}
inline bool isprime(const unsigned& x) {
	if (x <= prime[qty_of_prime - 1])return binary_search(prime, prime + qty_of_prime, x);
	else {
		unsigned t = sqrt(x);
		for (unsigned j = 0; prime[j] <= t; ++j) {
			if (x % prime[j] == 0) { return false; }
		}
		return true;
	}
}
inline void enumerate(const unsigned& p, const unsigned& q) {
	if (q == k) { if (isprime(s))++c; }
	else for (unsigned i = p; i <= n; ++i) {
		if (selected[i] == 0) {
			selected[i] = 1, s += x[i], enumerate(i + 1, q + 1), s -= x[i], selected[i] = 0;
		}
	}
}
int main() {
	genprime();
	scanf("%u%u", &n, &k);
	for (unsigned i = 1; i <= n; ++i)scanf("%u", &x[i]);
	enumerate(1, 0);
	printf("%u\n", c);
	return 0;
}