2771: 再组合质数

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：12 解决：7

题目描述

33DAI 想从 n 个不同的数中选取一些数，假设选取了 k 个数，选区的第 i 个数为 a_i，那么 33DAI 会算出

X=a_1+2a_2+3a_3+...+ia_i+...+(k-1)a_{k-1}+ka_k
X=a1+2a2+3a3+...+iai+...+(k−1)ak−1+kak

33DAI 希望 X 为质数，请问 33DAI 有多少种选择方法？

（如果两种方案选出来的数不同，或者数相同但顺序不同，就认为是不同的方案）

输入

输入第一行为一个整数 n，表示有 n 个数。

接下来一行为空格隔开的 n 个正整数，表示这 n 个数。

输出

输出一行，为一个整数，即有多少种选择方案可以选一组数使得 X 为质数。

样例输入 复制 

3
1 2 3

样例输出 复制 

10

提示

3
1 2 3 
10 
5
1 2 3 4 5 
94

样例 1 说明 

5 =  1 * 1 + 2 * 2 
7 =  1 * 1 + 2 * 3
13 =  1 * 1 + 2 * 3 + 3 * 2
2 =  1 * 2
13 =  1 * 2 + 2 * 1 + 3 * 3
11 =  1 * 2 + 2 * 3 + 3 * 1
3 =  1 * 3
5 =  1 * 3 + 2 * 1
11 =  1 * 3 + 2 * 1 + 3 * 2
7 =  1 * 3 + 2 * 2

数据范围

对于 60\% 的数据：1\le n\le 3；

对于 100\% 的数据：1\le n \le 9，1\le 每个数 \le 5\times 10^4

来源/分类

提交提交记录统计露一手!