/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は、正の整数 n を先頭に 0 を付けない通常の十進法で表したときの、各桁の数字の積を f(n) と定義しました。例えば、 f(234) = 2 \times 3 \times 4 = 24 であり、 f(5) = 5 です。いずれかの桁に 0 を含む場合は f(n) = 0 となります。例えば、 f(102) = 1 \times 0 \times 2 = 0 です。
高橋君は、 L 以上 R 以下の整数 n のうち、 f(n) = K を満たすものの個数を知りたくなりました。この個数を求めてください。
制約
- 1 \leq L \leq R \leq 10^{18}
- 0 \leq K \leq 10^{18}
- L, R, K は整数
入力
L R K
- 範囲の下限を表す整数 L 、範囲の上限を表す整数 R 、各桁の数字の積の目標値を表す整数 K が、スペース区切りで 1 行に与えられる。
出力
L 以上 R 以下の整数 n のうち、 f(n) = K を満たすものの個数を 1 行で出力せよ。
入力例 1
1 20 2
出力例 1
2
入力例 2
1 30 0
出力例 2
3
入力例 3
100 10000 36
出力例 3
93
入力例 4
123456789012 987654321098765432 720
出力例 4
32671066
入力例 5
1000000000000000000 1000000000000000000 0
出力例 5
1
Score : 466 pts
Problem Statement
Takahashi defined f(n) as the product of the digits of a positive integer n when written in standard decimal notation without leading zeros. For example, f(234) = 2 \times 3 \times 4 = 24 and f(5) = 5. If any digit is 0, then f(n) = 0. For example, f(102) = 1 \times 0 \times 2 = 0.
Takahashi wants to know the number of integers n between L and R (inclusive) that satisfy f(n) = K. Find this count.
Constraints
- 1 \leq L \leq R \leq 10^{18}
- 0 \leq K \leq 10^{18}
- L, R, K are integers
Input
L R K
- An integer L representing the lower bound of the range, an integer R representing the upper bound of the range, and an integer K representing the target value of the product of digits are given on a single line separated by spaces.
Output
Output in one line the number of integers n between L and R (inclusive) that satisfy f(n) = K.
Sample Input 1
1 20 2
Sample Output 1
2
Sample Input 2
1 30 0
Sample Output 2
3
Sample Input 3
100 10000 36
Sample Output 3
93
Sample Input 4
123456789012 987654321098765432 720
Sample Output 4
32671066
Sample Input 5
1000000000000000000 1000000000000000000 0
Sample Output 5
1