#P2118. 墨墨的等式

墨墨的等式

题目描述

墨墨突然对等式很感兴趣,他正在研究 ∑i=1n​ai​xi​=b 存在非负整数解的条件,他要求你编写一个程序,给定 n,{an​},l,r,求出有多少 b∈[l,r] 可以使等式存在非负整数解。

输入格式

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

第二行 n 个整数 {an​}。

输出格式

输出一个整数,表示有多少 b 可以使等式存在非负整数解。

样例输入

2 5 10
3 5

样例输出

5

数据规模与约定

对于 100% 的数据,n≤12,0≤ai​≤5×105,1≤l≤r≤1012。