Đếm căn theo lớp dư - EP1 (Counting Square Roots by Residue Class - EP1)

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

Đề bài

Cho bốn số nguyên $L,R,M,r$ với $0 \le r < M$.

Cần đếm số nguyên dương $k$ thỏa mãn đồng thời:

và

Input

Một dòng chứa bốn số nguyên $L,R,M,r$.

Output

In một số nguyên duy nhất: số lượng số nguyên dương $k$ thỏa mãn cả hai điều kiện.

Subtask

• Subtask 1 (25 điểm): $R \le 10^6$.
• Subtask 2 (35 điểm): đoạn các căn nguyên cần xét có độ dài không quá $10^6$.
• Subtask 3 (40 điểm): $1 \le L \le R \le 10^{18}$, $1 \le M \le 10^9$, $0 \le r < M$.

Ví dụ

Ví dụ 1

Input

1 30 2 0

Output

2

Giải thích

Các căn dương có bình phương trong $[1,30]$ là $1,2,3,4,5$. Trong số đó, các giá trị có dư 0 modulo 2 là 2 và 4, nên đáp án bằng 2.

Ví dụ 2

Input

10 100 2 1

Output

3

Giải thích

Điều kiện bình phương cho $4 \le k \le 10$. Các số lẻ trong đoạn này là 5, 7, 9, nên có 3 giá trị.

Ví dụ 3

Input

1 100 3 1

Output

4

Giải thích

Trong $1 \le k \le 10$, các số có dư 1 khi chia cho 3 là 1, 4, 7, 10. Vì vậy đáp án bằng 4.

Ví dụ 4

Input

50 80 5 0

Output

0

Giải thích

Chỉ có $k=8$ có bình phương nằm trong $[50,80]$, nhưng $8 \bmod 5=3$, nên không có giá trị thỏa mãn.

Ví dụ 5

Input

999998000001 1000000000000 1000000 0

Output

1

Giải thích

Các căn nguyên ở biên là 999999 và 1000000. Chỉ 1000000 có dư 0 modulo 1000000, nên đáp án bằng 1.