记录编号	173886	评测结果	AAAAA
题目名称	[NOIP 2002]选数	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-07-30 15:20:25	内存使用	0.31 MiB

#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

ifstream fin("choose.in");
ofstream fout("choose.out");
#define cin fin
#define cout fout
const int MAXN(21);
int k, n, x[MAXN], tot = 0, nt = 0;
void dfs(int, int);
bool pd[MAXN] = {false}, prime(int), ss[MAXN] = {false};

main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; ++i)
		cin >> x[i];
	
	ss[0] = ss[1] = false;
	ss[2] = ss[3] = ss[5] = ss[7] = true;
	dfs(1, 0);
	
	cout << tot;
	fin.close();
	fout.close();
//	for(;;);
}

void dfs(int a, int m)
{
	for (int i = m + 1; i <= n; ++i)
		if (! pd[i]){
			pd[i] = true;
			nt += x[i];
			if (a == k)
				if (prime(nt))
					tot++;
			if (a < k)
				dfs(a + 1, i);
			pd[i] = false;
			nt -= x[i];
		}
}

bool prime(int a)
{
	if (a == 1 || a == 0)
		return false;
	for (int i = 2; i <= (int)sqrt((double)a); ++i)
		if (a % i == 0)
			return false;
	return true;
}