Mật Khẩu của Xuân Thiên
Xem PDF
Điểm:
1900 (p)
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Xuân Thiên tạo một mật khẩu là số nguyên dương \(N\).
Một số được gọi là đẹp nếu tích các chữ số của nó chia hết cho tổng các chữ số của nó.
Hãy đếm có bao nhiêu số đẹp trong đoạn từ \(1\) đến \(N\).
Input
- Một dòng duy nhất chứa số nguyên dương \(N\).
Output
- In ra một số nguyên duy nhất là số lượng số đẹp trong đoạn \([1, N]\).
Example
Test 1
Input
20Output
11Note
Các số đẹp trong đoạn từ \(1\) đến \(20\) là: \(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20\).
- Các số từ \(1\) đến \(9\) luôn là số đẹp vì tích bằng tổng (tích chia hết cho tổng).
- Số \(10\) có tích là \(0\), tổng là \(1\) (\(0\) chia hết cho \(1\)) nên \(10\) là số đẹp.
- Số \(12\) có tích các chữ số là \(1 \cdot 2 = 2\), tổng các chữ số là \(1 + 2 = 3\). Vì \(2\) không chia hết cho \(3\) nên \(12\) không phải số đẹp.
- Số \(20\) có tích \(0\), tổng \(2\) (\(0\) chia hết cho \(2\)) nên \(20\) là số đẹp.
Constraints
- \(1 \le N \le 10^{18}\)
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(N \le 10^5\).
- Subtask \(2\) (\(30\%\) số điểm): \(N \le 10^9\).
- Subtask \(3\) (\(50\%\) số điểm): \(N \le 10^{18}\).
Bình luận