1008 选数 2002年NOIP全国联赛普及组
1008 选数
2002年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
查看运行结果
题目描述 Description
已知 n 个整数 x1,x2,…,xn，以及一个整数 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）。
输入描述 Input Description
键盘输入，格式为： n , k （1<=n<=20，k＜n） x1,x2，…,xn （1<=xi<=5000000）
输出描述 Output Description
屏幕输出，格式为： 一个整数（满足条件的种数）。
样例输入 Sample Input
4 3 3 7 12 19
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
（1<=n<=20，k＜n） （1<=xi<=5000000）
注意：可以用记录前驱结点的方法来判重
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=10001;
7 int a[MAXN];
8 int tot=0;
9 int ans[MAXN];
10 int vis[MAXN];
11 int now=1;
12 int n,m;
13 int num;
14 int flag[MAXN];
15 int pd(int n)
16 {
17 for(int i=2;i<=sqrt(n);i++)
18 {
19 if(n%i==0)
20 return 0;
21 }
22 return 1;
23 }
24 void dfs(int p,int ed)
25 {
26 if(p==m)
27 {
28 int maxn=0;
29 for(int i=1;i<=m;i++)
30 {
31 maxn=maxn+ans[i];
32 }
33 if(pd(maxn)==1)
34 {
35 num++;
36 }
37 return ;
38 }
39 for(int i=ed;i<=n;i++)
40 {
41 ans[now]=a[i];
42 now++;
43 flag[i]=1;
44 dfs(p+1,i+1);
45 now--;
46 ans[now]=0;
47 flag[i]=0;
48 }
49 }
50 int main()
51 {
52 scanf("%d%d",&n,&m);
53 for(int i=1;i<=n;i++)
54 {
55 scanf("%d",&a[i]);
56 tot=tot+a[i];
57 }
58 /*for(int i=2;i<=sqrt(tot);i++)
59 {
60 if(vis[i]==0)
61 {
62 for(int j=i*i;j<=tot;j=j+i)
63 {
64 vis[j]=1;
65 }
66
67 }
68 }*/
69 dfs(0,1);
70 printf("%d",num);
71 return 0;
72 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-04-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录