← 返回题目列表

AtCoder · abc182_f

F. 有效付款

中文机器翻译题面 查看原题

分数: 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