#67. 【82课】【3456】选数
【82课】【3456】选数
说明
已知 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>�</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>�</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mtext> </mtext><mo separator="true">,</mo><msub><mi>�</mi><mi>�</mi></msub></mrow></semantics></math>x1,x2,⋯,xn,以及 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>k(<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo><</mo><mi>�</mi></mrow></semantics></math>k<n)。从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数中任选 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>k 个整数相加,可分别得到一系列的和。例如当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>=</mo><mn>4</mn></mrow></semantics></math>n=4,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>=</mo><mn>3</mn></mrow></semantics></math>k=3,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>4</mn></mrow></semantics></math>4 个整数分别为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo separator="true">,</mo><mn>7</mn><mo separator="true">,</mo><mn>12</mn><mo separator="true">,</mo><mn>19</mn></mrow></semantics></math>3,7,12,19 时,可得全部的组合与它们的和为:
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>12</mn><mo>=</mo><mn>22</mn></mrow></semantics></math>3+7+12=22
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>29</mn></mrow></semantics></math>3+7+19=29
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>7</mn><mo>+</mo><mn>12</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>38</mn></mrow></semantics></math>7+12+19=38
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>12</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>34</mn></mrow></semantics></math>3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>+</mo><mn>7</mn><mo>+</mo><mn>19</mn><mo>=</mo><mn>29</mn></mrow></semantics></math>3+7+19=29。
输入格式
第一行两个空格隔开的整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>n,k(<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>�</mi><mo>≤</mo><mn>20</mn></mrow></semantics></math>1≤n≤20,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo><</mo><mi>�</mi></mrow></semantics></math>k<n)。
第二行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数,分别为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>�</mi><mn>1</mn></msub><mo separator="true">,</mo><msub><mi>�</mi><mn>2</mn></msub><mo separator="true">,</mo><mo>⋯</mo><mtext> </mtext><mo separator="true">,</mo><msub><mi>�</mi><mi>�</mi></msub></mrow></semantics></math>x1,x2,⋯,xn(<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><msub><mi>�</mi><mi>�</mi></msub><mo>≤</mo><mn>5</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>6</mn></msup></mrow></semantics></math>1≤xi≤5×106)
输出格式
对于每组输入数据,输出一个整数,表示满足条件的种数。
样例
4 3
3 7 12 19
1
提示
NOIP 2002 普及组第二题