Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Cho số nguyên dương ~N~ và số nguyên dương ~K~ ~(0 < N \le 2 \times 10^9;\ 1 \le K \le 82)~. ~M~ là tổng giá trị các chữ số của ~N~. ~N~ được gọi là số may mắn nếu ~M~ chia hết cho ~K~. Ví dụ: ~N = 234~ và ~K = 3~ thì ~N~ là số may mắn vì ~N~ có tổng các chữ số là ~M = 2 + 3 + 4 = 9~ chia hết cho 3.

Cho 2 số nguyên dương ~P~ và ~Q~ ~(0 < P \le Q \le 2 \times 10^9)~.

Yêu cầu: Hãy đếm số lượng các số may mắn nằm trong đoạn ~[P, Q]~.

Dữ liệu vào

• Gồm 1 dòng chứa 3 số ~P~, ~Q~, ~K~, mỗi số cách nhau 1 dấu cách.

Kết quả

• Gồm 1 dòng chứa số ~D~ là số lượng các số may mắn tìm được.

Giới hạn

• ~0 < P \le Q \le 2 \times 10^9~, ~1 \le K \le 82~.

Sample Input 1

1 30 3

Sample Output 1

10

Giải thích

Các số may mắn là ~3, 6, 9, 12, 15, 18, 21, 24, 27, 30~.

Sample Input 2

10 30 10

Sample Output 2

2

Giải thích

Cần tổng chữ số là 10 hoặc 20. Trong đoạn ~[10, 30]~ chỉ có ~19~ (~1 + 9 = 10~) và ~28~ (~2 + 8 = 10~).