AT_abc182_f [ABC182F] Valid payments

题目描述

在 AtCoder 国，有 $N$ 种硬币，面值分别为 $A_1$、$A_2$、$A_3$、$\dots$、$A_N$。其中 $A_1=1$，并且对于所有满足 $1 \le i < N$ 的整数 $i$，都有 $A_i < A_{i+1}$ 且 $A_{i+1}$ 是 $A_i$ 的倍数。

在这个国家的一家商店里，小狗“ルンルン”为了购买价值 $X$ 日元的商品，向店员支付了 $y$ 日元（$y \ge X$），店员作为找零返还了 $y - X$ 日元（找零可能为 $0$ 日元）。 此时，无论是ルンルン支付还是店员找零，双方都使用了最少数量的硬币来完成金额的支付。 此外，ルンルン支付的硬币中所用的任意一种面值，店员找零时都不会返还同样面值的硬币。

给定 $X$，请你求出所有可能的 $y$ 值有多少种。

输入格式

输入以如下格式从标准输入读入。

$N\ X\ A_1\ A_2\ A_3\ \dots\ A_N$

输出格式

请输出所有可能的 $y$ 值的种数。

输入输出样例 #1

输入 #1

3 9
1 5 10

输出 #1

3

输入输出样例 #2

输入 #2

5 198
1 5 10 50 100

输出 #2

5

输入输出样例 #3

输入 #3

4 44
1 4 20 100

输出 #3

4

输入输出样例 #4

输入 #4

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

输出 #4

21

说明/提示

限制条件

• $1 \le N \le 50$
• $1 = A_1 < A_2 < A_3 < \dots < A_N \le 10^{15}$
• $A_{i+1}$ 是 $A_i$ 的倍数（$1 \le i < N$）
• $1 \le X \le 10^{15}$
• 所有输入均为整数

样例解释 1

作为 $y$ 的可能值有 $9, 10, 14$。例如，当 $y=14$ 时，ルンルン支付了 $1$ 枚 $10$ 日元硬币和 $4$ 枚 $1$ 日元硬币，店员用 $1$ 枚 $5$ 日元硬币找零。在这种情况下，ルンルン支付的所有硬币面值，店员都没有返还，因此满足条件。

样例解释 2

作为 $y$ 的可能值有 $198, 200, 203, 208, 248$。

样例解释 3

作为 $y$ 的可能值有 $44, 60, 100, 104$。

由 ChatGPT 4.1 翻译