Đếm số không chia hết (Count Non-Multiples)

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]$ không 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à $X$ không chia hết cho $K$.

Subtask

• Subtask 1 (30 điểm):
  • $1 \le L \le R \le 10^{18}$.
  • $R-L \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

1 10 3

Output

7

Giải thích

Đoạn có $10$ số. Có $\lfloor10/3\rfloor=3$ số chia hết cho $3$, nên còn $10-3=7$ số.

Ví dụ 2

Input

8 8 4

Output

0

Giải thích

Đoạn chỉ có số $8$ và $8$ chia hết cho $4$, nên không có số nào thỏa yêu cầu.

Ví dụ 3

Input

100 110 50

Output

10

Giải thích

Đoạn có $11$ số và chỉ có $100$ chia hết cho $50$, nên có $10$ số không chia hết.