P1036 [NOIP 2002 普及组] 选数
题目描述
已知 n 个整数 x1,x2,…,xn,以及一个整数 k(k<n)。从这 n 个整数中任选 k 个整数相加,可以得到一系列的和。
现在要求你计算出,这些和中为素数的共有多少种。
∙质数:大于 1 且只能被 1 和它本身整除的正整数称为质数。特别地,1 不是质数。
例如当 n=4、k=3、四个整数分别为 3,7,12,19 时,全部选法与它们的和为:
∙3+7+12=22;
∙3+7+19=29;
∙3+12+19=34;
∙7+12+19=38。
其中只有 29 是素数,因此答案为 1。
输入格式
第一行输入两个整数 $n, k \left(2 \leqq n \leqq 20;\ 1 \leqq k < n\right)$,分别代表整数的个数与每次选取的个数。
第二行输入 n 个整数 $x_1, x_2, \dots, x_n \left(1 \leqq x_i \leqq 5 \times 10^6\right)$ 代表给定的整数。
输出格式
输出一行一个整数,代表和为素数的选法数量。
测试样例
4 3
3 7 12 19
1
样例 1 解释
从 4 个数中选 3 个,共有 (34)=4 种选法,对应的和分别是 22、29、34、38。
其中 22=2×11、34=2×17、38=2×19 都是合数,只有 29 是素数,因此答案为 1。
5 2
2 4 6 8 10
0
样例 2 解释
任取两个数,和都是偶数且不小于 2+4=6,因此全部为合数,答案为 0。
提示
对于 100% 的数据,2≦n≦20,1≦k<n,1≦xi≦5×106。
所有 xi 之和不超过 108,选法的数量不超过 (1020)=1.84756×105,枚举全部 k 元组合即可。