Mã hóa

Trong quá trình nghiên cứu các thuật toán mã hóa, Nam cần giải quyết bài toán sau:

Cho bốn số nguyên dương L, R, A, K. Hãy đếm số lượng số nguyên dương S thỏa mãn L <= S <= R và (A * S) % K = 0, trong đó % là phép toán chia lấy dư.

Hãy giúp Nam giải quyết bài toán này.

Đầu vào:

• Một dòng duy nhất chứa bốn số nguyên dương L, R, A, K (L <= R), các số được ngăn cách bởi dấu cách.

Đầu ra:

• In ra một số nguyên duy nhất là số lượng số nguyên S thỏa mãn điều kiện.

Ví dụ 1:

Đầu vào:

1 10 2 10

Đầu ra:

2

Ràng buộc:

• Subtask 1 (50% số điểm): L, R, A, K <= 10^6
• Subtask 2 (50% số điểm): L, R, A, K <= 10^18