F - 有效支付

得分: $600$ 分

问题描述

在AtCoder共和国，有$N$种硬币：1 到 N 分别代表的是 A1 到 AN 元硬币。
这里，$A_1 = 1$，对于每个$1 \le i \lt N$，有$A_i \lt A_{i + 1}$并且 $A_{i + 1}$ 是 $A_i$ 的倍数。

在这个国家的某个商店，Lucy狗通过将y元支付给出纳员并且从出纳员那里得到了y - X元的找零购买了一件X元的商品。（找零可能为0）。
在这里，Lucy和出纳员使用了表示这些金额所需的最小数量的硬币。
此外，出纳员不会找零给Lucy任何她支付的钱的硬币。

给定X，找到y的可能值的数量。

约束

• $1 \le N \le 50$
• $1 = A_1 \lt A_2 \lt A_3 \lt \dots \lt A_N \le 10^{15}$
• $A_{i + 1}$ 是 $A_i$的倍数。$(1 \le i \lt N)$
• $1 \le X \le 10^{15}$
• 输入中的所有数值均为整数。

输入

输入以如下格式从标准输入给出：

$N$ $X$

$A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots\ \hspace{5pt} A_N$

输出

打印y的可能值的数量。

3 9
1 5 10

3

y可以是9，10或14。
例如，当$y = 14$时，Lucy给出了一个10元硬币和四个1元硬币，并且出纳员找零一个5元硬币。
在这里出纳员没有找零给Lucy任何她支付的钱的硬币，满足要求。

5 198
1 5 10 50 100

5

y可以是198，200，203，208或248。

4 44
1 4 20 100

4

y可以是44，60，100或104。

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

21