← 返回题目列表

AtCoder · utpc2023_j

J. 日本礼金

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

配点 : 100 点

問題文

N 有几种纸币,i 第几种纸币是 A_i 日元钞票。每种纸币都有 10^{100} 张。在这里 A_1 < A_2 < \cdots < A_N 并且,每 i \: (1 \leq i \leq N - 1) 反对 A_{i+1} 是 您也可以写 A_i 的倍数。 给出了

我们考虑从这些纸币中选择几张放入袋子里。

在将纸币放入袋子的方法中,满足以下条件的方法称为、x 圆的好的放入方式称为。

  • 放入袋子的纸币总金额是 x 这是日元。
  • 从放入袋子的纸币中选择几张,其总金额为 \dfrac{x}{2} 日元的方法不存在。

另外,x 日元为好的金额意味着x 圆的好的放入方式表示其存在。

L 円以上 R 在不超过日元的金额中,好的金额有多少个,请求出。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 60
  • 1 \leq L \leq R \leq 10^{18}
  • 1 = A_1 < A_2 < \cdots < A_N \leq 10^{18}
  • A_{i+1} 是 您也可以写 A_i 的倍数 (1 \leq i \leq N - 1)

入力

输入是按以下格式从标准输入给出的。

N L R
A_1 A_2 \ldots A_N

出力

答案 请打印除以 1 行输出。


入力例 1

3 20 30
1 5 10

出力例 1

8

例如 第 10 日元钞票 我有 3 如果放入张数为 30 圆的好的放入方式,所以30 日元是好的金额。

一方、20 圆的好的放入方式不存在,所以20 日元是好的金额。 您将收到

21, 23, 25, 26, 27, 28, 29, 30 圆的 8 个是答案。


入力例 2

8 500007484602844543 985892611352151235
1 1971 151767 10927224 87417792 118975614912 263174060185344 43686893990767104

出力例 2

483957600323779237