DQCB02 — CHỮ SỐ BÍ MẬT

Đề bài

Cho một số nguyên không âm $N$ và một chữ số $K$ (từ $0$ đến $9$).

Hãy đếm xem chữ số $K$ xuất hiện bao nhiêu lần trong cách viết thập phân thông thường của $N$ (không có số $0$ vô nghĩa ở đầu).

Lưu ý: Số $0$ có đúng một chữ số là $0$. Vì vậy, với $N=0$ và $K=0$, kết quả là $1$.

Trong buổi luyện tập này, học sinh được yêu cầu sử dụng đệ quy trên chữ số.

Dữ liệu vào

Một dòng chứa hai số nguyên $N$ và $K$, cách nhau bằng một dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là số lần xuất hiện của chữ số $K$ trong $N$.

Giới hạn

• $0 \le N \le 10^{18}$.
• $0 \le K \le 9$.

Ví dụ 1

Input

1202202 2

Output

4

Ví dụ 2

Input

0 0

Output

1

Gợi ý tư duy đệ quy

Gọi dem(n, k) là số lần chữ số k xuất hiện trong n.

1. n % 10 cho biết điều gì?
2. n / 10 (chia nguyên) tạo ra bài toán con nào?
3. Nếu chữ số cuối bằng k, phải cộng thêm bao nhiêu?
4. Tại sao nên xét riêng trường hợp n < 10 để xử lý chính xác n = 0?