# [WC2020]猜数游戏

## 输入输出样例

### 输入样例 #1

4 7
1 3 4 6


### 输出样例 #1

17

### 输入样例 #2

8 9
1 2 3 4 5 6 7 8

### 输出样例 #2

532

## 说明

#### 样例1解释 下表给出了小 J 所选的子集与小 M 最小询问次数的关系： | 小 J 所选的子集 | 最优的询问集合 | | ------------------------------------------------------------ | -------------- | | $\{1\}$ | $\{1\}$ | | $\{3\}, \{3, 4\}, \{3, 6\}, \{3, 4, 6\}, \{1, 3\}, \{1, 3, 4\}, \{1, 3, 6\}, \{1, 3, 4, 6\}$ | $\{3\}$ | | $\{4\}, \{1, 4\}$ | $\{4\}$ | | $\{6\}, \{1, 6\}$ | $\{6\}$ | | $\{4, 6\}, \{1, 4, 6\}$ | $\{4,6\}$ | 因此最小询问次数的期望 $S = \frac{17}{15}$。 #### 数据范围 对于所有测试点：$1 \leq n \leq 5000$，$3 \leq p \leq 10^8$，$1 \leq a_i < p\ (1 \leq i \leq n)$ 且 $a_i$ 两两不同。 对于所有编号为奇数的测试点，保证 $p$ 是一个素数；对于所有编号为偶数的测试点，保证存在奇素数 $q$ 和正整数 $k > 1$ 使得 $p = q^k$。 | 测试点编号 | $n\leq$ | $p\le$ | 特殊性质 | 测试点编号 | $n\leq$ | $p\le$ | 特殊性质 | | ---------- | ------- | ------ | -------- | ---------- | ------- | ------ | -------- | | $1$ | $10$ | $100$ | 无 | $2$ | $10$ | $100$ | 无 | | $3$ |$10$|$100$|无| $4$|$10$|$100$|无| | $5$ | $200$ | $5000$|无 | $6$ | $200$ | $5000$ | 无 | | $7$ | $300$ | $10^6$ |无| $8$ | $300$ | $10^6$ | 无| | $9$|$300$ |$10^6$ | A| $10$ | $300$ | $10^6$ |B| | $11$ | $5000$ | $10^7$ |A| $12$ | $5000$ | $10^7$ | 无 | | $13$|$5000$|$10^7$ | 无 | $14$ | $5000$|$10^7$| 无| | $15$|$5000$ | $10^8$ | A | $16$ | $5000$|$10^8$ | B| | $17$ | $5000$|$10^8$|无 | $18$ |$5000$|$10^8$| 无 | | $19$ | $5000$|$10^8$|无 | $20$ |$5000$|$10^8$| 无 | 特殊性质 A：在模 $p$ 意义下 $3^i\ (1 \leq i \leq p - 1)$ 两两不同余。 特殊性质 B：对所有的 $1 \leq i \leq n$ 都有 $(a_i, p) > 1$。