Champernowne Count

시간 제한1초메모리 제한1024 MB

요약

1부터 i까지 이어 붙인 i번째 Champernowne 단어 중 처음 n개 가운데 k로 나누어떨어지는 것의 개수를 센다.

난이도: 보통10점 중 6점
유형: 수학, 정수론, 구현, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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$ .

입력

The single line of input contains two integers, $n$ $(1 \le n \le 10^5)$ and $k$ $(1 \le k \le 10^9)$ .

출력

Output a single integer, which is a count of the first $n$ Champernowne words divisible by $k$ .

예제4

예제 1
입력
```
4 2
```
예상 출력
```
2
```
예제 2
입력
```
100 7
```
예상 출력
```
14
```
예제 3
입력
```
314 159
```
예상 출력
```
4
```
예제 4
입력
```
100000 999809848
```
예상 출력
```
1
```