Mã hóa - ENCRYPTION

Khi nghiên cứu xây dựng thuật toán mã hóa, Nam cần giải quyết bài toán sau: Với bốn số nguyên dương $L,R,A,K,$ cần đếm số lượng số nguyên dương $S$ mà $L\le S\le R$ và $(A\ast S)$ $mod$ $K$ $=0$, trong đó $mod$ là phép toán chia lấy dư.

Hãy giúp Nam giải bài toán trên.

Yêu cầu:

Đếm số lượng số nguyên dương $S$ thỏa yêu cầu bài toán

Dữ liệu (Vào từ tệp ENCRYPTION.INP):

• Dòng duy nhất chứa $4$ số nguyên dương $L,R,A,K$ $(1\le L,R,A,K\le {10}^{18};L\le R)$.

Kết quả (Xuất ra tệp ENCRYPTION.OUT):

• Gồm một số nguyên dương duy nhất là kết quả bài toán

Ví dụ:

<testlist> <test> <inp> 1 10 2 10 </inp> <out> 2 </out> <note> Có $2$ số thỏa yêu cầu bài toán là $5$ và $10$. </note> </test> </testlist>

Subtask:

• $30\mathrm{\%}$ số test tương ứng với $30\mathrm{\%}$ số điểm có $1$ $\le L,R,K\le$ ${10}^6$ và $A=1$.
• $40\mathrm{\%}$ số test tương ứng với $40\mathrm{\%}$ số điểm có $1$ $\le L,R,A,K\le$ ${10}^6$.
• $30\mathrm{\%}$ số test còn lại tương ứng với $30\mathrm{\%}$ số điểm không có ràng buộc gì thêm.