Bội riêng (Exclusive Multiples)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho bốn số nguyên dương $L, R, A, B$ với $L \le R$.

Một số nguyên $x$ được gọi là bội riêng nếu $x$ chia hết cho đúng một trong hai số $A$ và $B$; tức là $x$ chia hết cho $A$ hoặc chia hết cho $B$, nhưng không đồng thời chia hết cho cả hai.

Hãy đếm số lượng bội riêng thuộc đoạn $[L,R]$.

Input

Một dòng chứa bốn số nguyên dương $L, R, A, B$, các số cách nhau bởi một dấu cách.

Output

In một số nguyên duy nhất là số lượng bội riêng trong đoạn $[L,R]$.

Subtask

• Subtask 1 (40%): $1 \le L \le R \le 10^6$, $1 \le A,B \le 10^9$.
• Subtask 2 (30%): $1 \le L \le R \le 10^{12}$, $1 \le A,B \le 10^9$.
• Subtask 3 (30%): $1 \le L \le R \le 10^{18}$, $1 \le A,B \le 10^9$.

Ví dụ

Ví dụ 1

Input

1 20 4 6

Output

6

Giải thích

Các số thỏa mãn là $4,6,8,16,18,20$. Số $12$ chia hết cho cả $4$ và $6$ nên không được tính.

Ví dụ 2

Input

10 30 5 10

Output

2

Giải thích

Các bội của $5$ trong đoạn là $10,15,20,25,30$. Các số $10,20,30$ cũng chia hết cho $10$ nên bị loại; còn lại $15$ và $25$.

Ví dụ 3

Input

7 9 2 3

Output

2

Giải thích

Trong đoạn $[7,9]$, số $8$ chỉ chia hết cho $2$ và số $9$ chỉ chia hết cho $3$, nên có đúng hai bội riêng.