Score : $500$ points

问题陈述

最多有多少个不大于 $N$ 的正整数，其各位数字的乘积不超过 $K$？

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:22:05