题目描述 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 #include2 using namespace std; 3 int n,k,ans,s[30]; 4 bool v[30010]; 5 void dfs(int x,int y,int z){ 6 if(y==k){ 7 if(!z||z==1||((z%2==0)&&z!=2)) return; 8 for(int i=3;i*i<=z;i+=2) 9 if(z%i==0) return;10 ans++;return;11 }12 for(int i=1;i<=n;i++){13 if(!v[i]&&i>x){14 v[i]=1;15 dfs(i,y+1,z+s[i]);16 v[i]=0;17 }18 }19 }20 int main(){21 scanf("%d%d",&n,&k);22 for(int i=1;i<=n;i++) scanf("%d",&s[i]);23 dfs(0,0,0);24 printf("%d\n",ans);25 return 0;26 }
不大會來著。