Đếm bội trong đoạn đầu (Count Multiples in a Prefix)

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

Đề bài

Cho hai số nguyên dương $N$ và $K$. Xét các số nguyên từ $1$ đến $N$. Một số được gọi là bội của $K$ nếu nó chia hết cho $K$. Hãy đếm có bao nhiêu bội của $K$ trong đoạn $[1,N]$.

Input

Một dòng chứa hai số nguyên dương $N$ và $K$.

Output

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

Subtask

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

Ví dụ

Ví dụ 1

Input

20 3

Output

6

Giải thích

Các bội không vượt quá $20$ là $3,6,9,12,15,18$, có $6$ số.

Ví dụ 2

Input

7 10

Output

0

Giải thích

Bội dương nhỏ nhất của $10$ là $10>7$, nên không có số nào cần đếm.

Ví dụ 3

Input

1000000000000000000 1000000000

Output

1000000000

Giải thích

Ta có $10^{18}\div 10^9=10^9$, nên có đúng $10^9$ bội.