E - Digit Products Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 以下の正の整数のうち、各桁の数字の積が K 以下であるものは何個ありますか？

制約

  • 1 \leq N \leq 10^{18}
  • 1 \leq K \leq 10^9
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N K

出力

条件を満たす整数の個数を出力せよ。

入力例 1

13 2

出力例 1

5

13 以下の正の整数のうち、各桁の数字の積が 2 以下であるものは 1,2,10,11,12 の 5 つです。

入力例 2

100 80

出力例 2

99

100 以下の正の整数のうち、99 以外のものが条件を満たします。

入力例 3

1000000000000000000 1000000000

出力例 3

841103275147365677

答えが 32 bit 整数に収まらない可能性があることに注意してください。

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.