Hide
Problem D
Champernowne Count
The $n$th Champernowne word is obtained by writing down the first $n$ positive integers and concatenating them together. For example, the 10th Champernowne word is “12345678910”.
Given two positive integers $n$ and $k$, count how many of the first $n$ Champernowne words are divisible by $k$.
Input
The single line of input contains two integers, $n$ $(1 \le n \le 10^5)$ and $k$ $(1 \le k \le 10^9)$.
Output
Output a single integer, which is a count of the first $n$ Champernowne words divisible by $k$.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 2 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
100 7 |
14 |
| Sample Input 3 | Sample Output 3 |
|---|---|
314 159 |
4 |
| Sample Input 4 | Sample Output 4 |
|---|---|
100000 999809848 |
1 |
