分数: 600 点
问题陈述
在 AtCoder 共和国, N 使用的硬币种类: A_1-日元, A_2-日元, A_3-日元, \dots, A_N- 日元硬币。
在这里, A_1 = 1 成立,并且对于每个 i 这样 1 \le i \lt N, A_i \lt A_{i + 1} 持有并 A_{i + 1} 是的倍数 A_i.
在这个国家的某家商店,小狗伦伦买了一个 X-日元产品给予 y\ (\ge X) 日元给店员并收到零钱 y - X 店员提供的日元。 (变化可能是 0 日元。)
这里,伦伦和店员都用了代表这些钱所需的最少数量的硬币。
此外,店员也没有归还伦伦给他的任何种类的硬币。
鉴于 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.
示例输入 1
3 9 1 5 10
示例输出 1
3
y 可以 9, 10,或 14.
例如,当 y = 14,伦伦给了一个 10-日元硬币和四个 1- 日元硬币,店员退还一枚 5- 日元硬币。
这里,店员没有退还伦伦给他的任何种类的硬币,满足要求。
示例输入 2
5 198 1 5 10 50 100
示例输出 2
5
y 可以 198, 200, 203, 208,或 248.
示例输入 3
4 44 1 4 20 100
示例输出 3
4
y 可以 44, 60, 100,或 104.
示例输入 4
9 11837029798 1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840
示例输出 4
21