Counting a Digit

Difficulty: 1600 2000 ms 128 MB

math

How many times does the digit D appear when all integers 1..N are written out?

Input: one line with two integers N and D.

Output: the number of occurrences of digit D in 1..N.

Constraints:

• 1 ≤ N ≤ 10¹⁸
• 0 ≤ D ≤ 9

Sample Tests

13 1

6

25 2

9

Read the Editorial