102084: [AtCoder]ABC208 E - Digit Products
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $500$ points
Problem Statement
For how many positive integers at most $N$ is the product of the digits at most $K$?
Constraints
- $1 \leq N \leq 10^{18}$
- $1 \leq K \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $K$
Output
Print the number of integers satisfying the condition.
Sample Input 1
13 2
Sample Output 1
5
Out of the positive integers at most $13$, there are five such that the product of the digits is at most $2$: $1$, $2$, $10$, $11$, and $12$.
Sample Input 2
100 80
Sample Output 2
99
Out of the positive integers at most $100$, all but $99$ satisfy the condition.
Sample Input 3
1000000000000000000 1000000000
Sample Output 3
841103275147365677
Note that the answer may not fit into a $32$-bit integer.