/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
AtCoder 国には A_1 円玉、A_2 円玉、A_3 円玉、\dots 、A_N 円玉の N 種類のコインがあります。
ここで A_1 = 1 であり、1 \le i \lt N を満たす全ての整数 i について、 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 枚と 1 円玉 4 枚を渡し、店員は 5 円玉 1 枚でお釣りを返します。
このとき、ルンルンが渡したどの種類のコインも店員は返していないので条件を満たします。
入力例 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
Score : 600 points
Problem Statement
In Republic of AtCoder, N kinds of coins are used: A_1-yen, A_2-yen, A_3-yen, \dots, A_N-yen coins.
Here, A_1 = 1 holds, and for each i such that 1 \le i \lt N, A_i \lt A_{i + 1} holds and A_{i + 1} is a multiple of A_i.
At some shop in this country, Lunlun the dog bought an X-yen product by giving y\ (\ge X) yen to the clerk and receiving the change of y - X yen from the clerk. (The change may have been 0 yen.)
Here, both Lunlun and the clerk used the minimum number of coins needed to represent those amounts of money.
Additionally, the clerk did not return any kind of coins that Lunlun gave him.
Given X, find the number of possible values for y.
Constraints
- 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} is a multiple of A_i. (1 \le i \lt N)
- 1 \le X \le 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X
A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots\ \hspace{5pt} A_N
Output
Print the number of possible values for y.
Sample Input 1
3 9 1 5 10
Sample Output 1
3
y can be 9, 10, or 14.
For example, when y = 14, Lunlun gives one 10-yen coin and four 1-yen coins, and the clerk returns one 5-yen coin.
Here, the clerk is not returning any kind of coins that Lunlun gives him, satisfying the requirement.
Sample Input 2
5 198 1 5 10 50 100
Sample Output 2
5
y can be 198, 200, 203, 208, or 248.
Sample Input 3
4 44 1 4 20 100
Sample Output 3
4
y can be 44, 60, 100, or 104.
Sample Input 4
9 11837029798 1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840
Sample Output 4
21