LG#P1036. [NOIP 2002 普及组] 选数

[NOIP 2002 普及组] 选数

P1036 [NOIP 2002 普及组] 选数

题目描述

\hspace{15pt}已知 nn 个整数 x1,x2,…,xnx_1,x_2,\dots,x_n,以及一个整数 k(k<n)k \left(k < n\right)。从这 nn 个整数中任选 kk 个整数相加,可以得到一系列的和。

\hspace{15pt}现在要求你计算出,这些和中为素数的共有多少种。

∙ \hspace{15pt}\bullet\,质数:大于 11 且只能被 11 和它本身整除的正整数称为质数。特别地,11 不是质数。

\hspace{15pt}例如当 n=4n=4、k=3k=3、四个整数分别为 3,7,12,193,7,12,19 时,全部选法与它们的和为:

∙ \hspace{23pt}\bullet\,3+7+12=223+7+12=22;

∙ \hspace{23pt}\bullet\,3+7+19=293+7+19=29;

∙ \hspace{23pt}\bullet\,3+12+19=343+12+19=34;

∙ \hspace{23pt}\bullet\,7+12+19=387+12+19=38。

\hspace{15pt}其中只有 2929 是素数,因此答案为 11。

输入格式

\hspace{15pt}第一行输入两个整数 $n, k \left(2 \leqq n \leqq 20;\ 1 \leqq k < n\right)$,分别代表整数的个数与每次选取的个数。

\hspace{15pt}第二行输入 nn 个整数 $x_1, x_2, \dots, x_n \left(1 \leqq x_i \leqq 5 \times 10^6\right)$ 代表给定的整数。

输出格式

\hspace{15pt}输出一行一个整数,代表和为素数的选法数量。

测试样例

4 3
3 7 12 19
1

样例 1 解释

\hspace{15pt}从 44 个数中选 33 个,共有 (43)=4\binom{4}{3} = 4 种选法,对应的和分别是 2222、2929、3434、3838。

\hspace{15pt}其中 22=2×1122 = 2 \times 11、34=2×1734 = 2 \times 17、38=2×1938 = 2 \times 19 都是合数,只有 2929 是素数,因此答案为 11。

5 2
2 4 6 8 10
0

样例 2 解释

\hspace{15pt}任取两个数,和都是偶数且不小于 2+4=62+4=6,因此全部为合数,答案为 00。

提示

\hspace{15pt}对于 100%100\% 的数据,2≦n≦202 \leqq n \leqq 20,1≦k<n1 \leqq k < n,1≦xi≦5×1061 \leqq x_i \leqq 5 \times 10^6。

\hspace{15pt}所有 xix_i 之和不超过 10810^8,选法的数量不超过 (2010)=1.84756×105\binom{20}{10} = 1.84756 \times 10^5,枚举全部 kk 元组合即可。