#P2371. [国家集训队] 墨墨的等式

[国家集训队] 墨墨的等式

题目描述

墨墨突然对等式很感兴趣,他正在研究 i=1naixi=b\sum_{i=1}^n a_ix_i=b 存在非负整数解的条件,他要求你编写一个程序,给定 n,a1n,l,rn, a_{1\dots n}, l, r,求出有多少 b[l,r]b\in[l,r] 可以使等式存在非负整数解。

输入格式

第一行三个整数 n,l,rn,l,r

第二行 nn 个整数 a1na_{1\dots n}

输出格式

一行一个整数,表示有多少 b[l,r]b\in[l,r] 可以使等式存在非负整数解。

2 5 10
3 5
5

提示

对于 20%20\% 的数据,n5n \le 5r10r \le 10

对于 40%40\% 的数据,n10n \le 10r106r \le 10^6

对于 100%100\% 的数据,n12n \le 120ai5×1050 \le a_i \le 5\times 10^51lr10121 \le l \le r \le 10^{12}