Number of Representable High#4571

Number of Representable High

1 second

256 megabytes

Hard

Given two integers $a$ and $b$ . A number $x$ is called representable if it can be written as the sum

x = x_{1} + x_{2} + \dots + x_{n}

x = x_1 + x_2 + \dots + x_n

for some finite (possibly zero) number of terms $x_{i}$ x_i, where each $x_{i}$ x_i is equal to either $a$ or $b$ .

Determine how many distinct numbers in the interval $[A, B]$ are representable.

Constraints

$a, b$ are integers such that $∣ a ∣ \leq 10000$ |a| \leq 10000, $∣ b ∣ \leq 10000$ |b| \leq 10000.
$A, B$ are integers such that $∣ A ∣ \leq 1 0^{18}$ |A| \leq 10^{18}, $∣ B ∣ \leq 1 0^{18}$ |B| \leq 10^{18}.
$A \leq B$ A \leq B.

Input

The input consists of a single line containing the integers $a$ , $b$ , $A$ , and $B$ .

Output the number of distinct numbers in the interval $[A, B]$ that are representable as sums of $a$ and $b$ .

Example 1

Loading

x = x_{1} + x_{2} + \dots + x_{n}

x_{i}

x_{i}

∣ a ∣ \leq 10000

∣ b ∣ \leq 10000

∣ A ∣ \leq 1 0^{18}

∣ B ∣ \leq 1 0^{18}

A \leq B