Nonnegative Integer Solutions of a Linear Equation

Given a linear equation (\sum_{i=1}^n a_i x_i = b) with nonnegative integer variables (x_i), determine how many values of (b) within the interval ([l, r]) admit at least one solution. More formally, you are given an integer (n), coefficients (a_1, a_2, \ldots, a_n) (each positive) and two integers (l) and (r). Count the number of (b \in [l, r]) such that there exists a solution in nonnegative integers (x_1,x_2,\dots,x_n) satisfying [ \sum_{i=1}^n a_i x_i = b. ] A key observation is to first compute (g=\gcd(a_1, a_2, \ldots, a_n)). If (g) does not divide (b), the equation has no solution. Otherwise, defining (a'_i = a_i/g) and (b' = b/g), the problem reduces to determining whether (b') is representable as a nonnegative integer combination of (a'_1,a'_2,\dots,a'_n). In the special case when one of the (a'_i) is 1, every sufficiently large number (indeed every number (\geq \min{a'_i})) is representable. For the general case, one can use a residue-Dijkstra algorithm modulo (m = \min(a'_1,\dots,a'_n)) to compute the minimum reachable value for each residue class. Then, for an integer (x) (where (b' = x)), if (x \geq D[r] ) (with (r=x \bmod m) and (D[r]) the computed minimum for residue (r)), the number is representable. Finally, the answer is the count of (b \in [l, r]) for which this condition holds.

inputFormat

The input consists of two lines. The first line contains an integer (n) and (n) space‐separated positive integers (a_1,a_2,\ldots,a_n). The second line contains two integers (l) and (r), representing the range in which to count valid (b) values.

outputFormat

Output a single integer: the number of values (b) in ([l,r]) for which the equation (\sum_{i=1}^n a_i x_i = b) has a nonnegative integer solution.

sample

2
4 6
1 20

9