Không chia hết

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Bạn được cho bốn số nguyên \(A\), \(B\), \(C\), và \(D\). Tìm số lượng các số nguyên từ \(A\) đến \(B\) (bao gồm cả hai) mà không chia hết cho cả \(C\) lẫn \(D\).

Input

A B C D

Output

In ra số lượng các số nguyên từ \(A\) đến \(B\) mà không chia hết cho cả \(C\) lẫn \(D\).

Ràng buộc

• \(1 \leq A \leq B \leq 10^{18}\)
• \(1 \leq C, D \leq 10^9\)
• Tất cả giá trị đầu vào là số nguyên.

Ví dụ 1

Input

4 9 2 3

Output

2

Giải thích ví dụ

Các số 5 và 7 thỏa mãn điều kiện.

Ví dụ 2

Input

10 40 6 8

Output

23

Giải thích ví dụ

• Ví dụ 1: Với dãy số từ 4 đến 9, các số 5 và 7 không chia hết cho cả 2 và 3, nên kết quả là 2.

• Ví dụ 2: Với dãy số từ 10 đến 40, có 23 số không chia hết cho cả 6 và 8.

Thông tin học tập

• Buổi: B08
• Concepts: LCM, arithmetic inclusion-exclusion
• Giới hạn kiến thức: B01-B08
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 30