Valid payments

题目描述

在 AtCoder 共和国，使用 $N$ 种硬币：$A_1$ 日元、$A_2$ 日元、$A_3$ 日元、$\dots$、$A_N$ 日元的硬币。
这里，$A_1 = 1$ 成立，并且对于每个满足 $1 \le i \lt N$ 的 $i$，有 $A_i \lt A_{i + 1}$ 且 $A_{i + 1}$ 是 $A_i$ 的倍数。
在该国的某个商店，狗狗 Lunlun 购买了一件價值 $X$ 日元的商品，他给店员支付了 $y\ (\ge X)$ 日元并从店员那里收到了找零 $y - X$ 日元。（找零可能为 $0$ 日元。）
这里，Lunlun 和店员都使用表示该金额所需的最少硬币数。
此外，店员没有归还 Lunlun 给他的任何种类的硬币。
给定 $X$，找出可能的 $y$ 的值的个数。

输入格式

输入从标准输入按以下格式给出： $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

5 198
1 5 10 50 100

5

4 44
1 4 20 100

4

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

21

提示

$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}$ 输入中的所有数值均为整数。$y$ 可以是 $9$、$10$ 或 $14$。
例如，当 $y = 14$ 时，Lunlun 给出一枚 $10$ 日元硬币和四枚 $1$ 日元硬币，店员找回一枚 $5$ 日元硬币。
这里，店员没有归还 Lunlun 给他的任何种类的硬币，满足该要求。
$y$ 可以是 $198$、$200$、$203$、$208$ 或 $248$。
$y$ 可以是 $44$、$60$、$100$ 或 $104$。

标签: AtCoder|abc182F

来源

AtCoder|abc182F