Mid-Central USA Programming Contest 2018

Start

2018-11-03 17:30 UTC

Mid-Central USA Programming Contest 2018

End

2018-11-03 22:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -45 days 4:31:06

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Coprime Integers

Given intervals $[a, b]$ and $[c, d]$, count the number of ordered pairs of co-prime integers $(x, y)$ such that $a \le x \le b$ and $c \le y \le d$. Coprime integers have no common factor greater than $1$.

Input

The input consists of a single line of four space-separated integers $a$, $b$, $c$, and $d$. These integers satisfy the bounds ($1 \le a \le b \le 10^7$, $1 \le c \le d \le 10^7$).

Output

Print a single integer: the number of coprime pairs $(x,y)$ with $a \le x \le b, c\le y \le d$.

Sample Input 1 Sample Output 1
1 5 1 5
19
Sample Input 2 Sample Output 2
12 12 1 12
4
Sample Input 3 Sample Output 3
1 100 1 100
6087