/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は、 1 から N までの整数について調べています。
正の整数 k を十進法で表記したとき、各桁の数字をすべて掛け合わせた値を k の「桁積」と呼ぶことにします。例えば、 123 の桁積は 1 \times 2 \times 3 = 6 、 205 の桁積は 2 \times 0 \times 5 = 0 、 9 の桁積は 9 です。
高橋君は、 1 以上 N 以下の整数のうち、桁積が 0 でなく、かつその桁積が M の倍数であるものの個数を知りたがっています。高橋君に代わって、この個数を求めてください。
なお、 0 はどんな正の整数の倍数でもないものとします（すなわち、桁積が 0 のものは常に数えません）。
制約
- 1 \leq N \leq 10^{18}
- 1 \leq M \leq 500
- N および M は整数である
入力
N M
調べる範囲の上限 N と、桁積が倍数であるかを判定する基準の値 M が、スペース区切りで 1 行に与えられる。
出力
1 以上 N 以下の整数のうち、桁積が 0 でなく、かつ桁積が M の倍数であるものの個数を 1 行で出力せよ。
入力例 1
25 6
出力例 1
3
入力例 2
20 7
出力例 2
2
入力例 3
12345 36
出力例 3
2767
入力例 4
987654321012345678 420
出力例 4
127763436760690150
入力例 5
1 1
出力例 5
1
Score : 433 pts
Problem Statement
Takahashi is investigating integers from 1 to N.
When a positive integer k is written in decimal notation, the product of all its digits is called the "digit product" of k. For example, the digit product of 123 is 1 \times 2 \times 3 = 6, the digit product of 205 is 2 \times 0 \times 5 = 0, and the digit product of 9 is 9.
Takahashi wants to know the number of integers between 1 and N (inclusive) whose digit product is not 0 and whose digit product is a multiple of M. Find this count on behalf of Takahashi.
Note that 0 is not a multiple of any positive integer (that is, integers whose digit product is 0 are never counted).
Constraints
- 1 \leq N \leq 10^{18}
- 1 \leq M \leq 500
- N and M are integers
Input
N M
The upper limit N of the range to investigate and the value M used to determine whether the digit product is a multiple are given on a single line, separated by a space.
Output
Output in one line the number of integers between 1 and N (inclusive) whose digit product is not 0 and whose digit product is a multiple of M.
Sample Input 1
25 6
Sample Output 1
3
Sample Input 2
20 7
Sample Output 2
2
Sample Input 3
12345 36
Sample Output 3
2767
Sample Input 4
987654321012345678 420
Sample Output 4
127763436760690150
Sample Input 5
1 1
Sample Output 5
1