Bài 2. BỘI SỐ ĐẶC BIỆT (5,0 điểm; Đề HSG9 tỉnh Tuyên Quang 2025-2026)

Bo đang luyện thi vào lớp 10 chuyên Tin của trường THPT chuyên A. Chủ đề thầy giáo giao cho Bo tuần này là số học, trong quá trình học tập Bo phát hiện ra một điều thú vị về bội của một số và đặt tên là Bội số đặc biệt. Với một số nguyên dương P không chia hết cho 2 và 5. Số X được gọi là một bội số đặc biệt của P nếu X chia hết cho P và X chỉ chứa toàn chữ số 9.

Ví dụ: Với P = 7 thì X = 999999 là một bội số đặc biệt của số P.
Cho trước hai số nguyên dương P và M.
Yêu cầu: Cho biết có bao nhiêu số X là bội số đặc biệt của P và X có số chữ số không vượt quá M.
Dữ liệu vào: Gồm hai số nguyên P và M trên cùng một dòng.
Dữ liệu ra: In ra một số duy nhất là số lượng các số X thỏa mãn yêu cầu.
Ví dụ:

Ràng buộc:

• Subtask 1 (60% số điểm): P < 10⁴, M ≤ 18.
• Subtask 2 (40% số điểm): 10⁴ ≤ P < 10⁶, M ≤ 10⁷.