Đếm bội trong một đoạn (Count Multiples in an Interval)

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

Đề bài

Cho ba số nguyên dương $L,R,K$ với $L\le R$. Hãy đếm số lượng số nguyên trong đoạn $[L,R]$ chia hết cho $K$.

Input

Một dòng chứa ba số nguyên dương $L$, $R$ và $K$.

Output

In ra số lượng số nguyên $X$ thỏa mãn $L\le X\le R$ và $K\mid X$.

Subtask

• Subtask 1 (30 điểm):
  • $1 \le L \le R \le 10^6$.
  • $1 \le K \le 10^{18}$.
• Subtask 2 (70 điểm):
  • $1 \le L \le R \le 10^{18}$.
  • $1 \le K \le 10^{18}$.

Ví dụ

Ví dụ 1

Input

5 20 4

Output

4

Giải thích

Trong đoạn có các bội $8,12,16,20$, nên kết quả là $4$.

Ví dụ 2

Input

1 10 20

Output

0

Giải thích

Bội dương nhỏ nhất của $20$ là $20$, lớn hơn $10$, nên kết quả bằng $0$.

Ví dụ 3

Input

1000000000000 1000000000100 25

Output

5

Giải thích

Các bội là $10^{12}$, $10^{12}+25$, $10^{12}+50$, $10^{12}+75$, $10^{12}+100$, tổng cộng $5$ số.