This editorial is mainly split into two parts.

• In the first half, we will explain an algorithm called Digit DP (Dynamic Programming), which reduces the contribution of \(N\) to the complexity from \(\mathrm{O}(N)\) to \(\mathrm{O}(\log N)\).
• In the second half, we will explain how to reduce the time complexity from \(\mathrm{O}(K \log N)\) to \(\mathrm{O}((\log K)^4 \log N)\).

1. Digit DP

For the problem like this, if we explicitly enumerate every integer one by one and compute it naively, it requires at least \(\mathrm{O}(N)\) time. As you can see from the constraints \(N \leq 10^{18}\), we need to construct an algorithm faster than linear time against \(N\).

Digit DP is a famous combinatorial algorithm to count fast the number of integers not exceeding \(N\) that is restricted by digital constraints.

Digit DP refers to a DP where we hold an additional state whether the first \(i\) digits determined so far is strictly less than those of \(N\).

• There are many editorials on the Internet of the detailed explanations of digit DP, so we will omit here. If you want to know about digit DP, please refer to the website that explains digit DP.

We consider solving the problem based on digit DP. There are some ways to hold a state; this time, we define DP table by

• \(\mathrm{dp} _{i, p} := \) The number of combinations of the first \(i\) digits (except for \(\bf 0\)), whose product is \(p\).

Also, let \(\mathrm{eq}_{i} :=\) (the product of the first \(i\) digits of \(N\)). Then we have the following DP relations described by the following pseudocode. (Note: a naive implementation of the following pseudocode will lead to TLE or MLE.)

# Python-like pseudocode
# for i in range(a, b) means the variable i is looped from a to b-1

# input : N, K
# output : answer
def calc(N, K):
  dp = (two-dimensional array initialized with 0)
  eq = (one-dimensional array initialized with 0)

  eq[0] = 1

  for i in range(1, (number of digits of N) + 1):
    # Let digit be the i-th digit of N
    digit = (the i-th digit of N)

    # (1) less -> less
    # When the first (i-1) digits are less than those of N
    # The i-th digit can be any of 0 to 9
    for p in range(0, dp[i]の長さ)
      for d in range(0, 10):
        dp[i + 1][p * d] += dp[i][p]

    # (2) equal -> less
    # When the first (i-1) digits are same to those of N, and the i-th digit is less than that of N
    # The i-th digit can be at least 0, and strictly less than `digit`
    for d in range(0, digit):
      # Exclude i = 0 and d = 0, since the entire integer becomes 0
      if i == 0 and d == 0:
        continue
      dp[i + 1][eq[i] * d] += 1

    # (3) equal -> equal
    # When the first i digits are same to those of N
    # The i-th digit is `digit` itself
    eq[i + 1] = eq[i] * digit

    # (4) 0...0d form
    # If the first (i-1)-th digit is 0 and the i-th is other than 0
    # The i-th digit d can be between 1 and 9, inclusive
		# (d = 0 is excluded, since the entire integer becomes 0)
    for d in range(1, 10):
      # The case where i = 0 is already counted in (2)
      if i == 0:
        continue
      dp[i + 1][d] += 1

  answer =  0
  for p in range(0, length of dp[(number of digits of N)]):
    if p <= K:
      answer += dp[(number of digits of N)][p]

  if eq[(number of digits of N)] <= K:
    answer += 1

  return ans

2. Optimization by reducing the number of states

Now that we have introduced digit DP, we have sped up this problem from a linear-time algorithm to logarithmic-time algorithm against \(N\). However, the number of states is enormous, so you cannot get AC.

One of the basic techniques to optimize such DP is to decrease the number of DP states utilizing the nature of the problem. Let’s go for this technique to decrease the number of states.

First, this problem requires to check if the product is more than \(K\) or not, so we can identify the states where \(p\) is greater than \(K\). Therefore, the state can be either of:

• the product of digits is \(0\)
• the product of digits is \(1, 2, \ldots, \) or \(K\)
• the product of digits is more than \(K\)

so that there are no more than \(K+2\) states. Thus the number of states can be \(\mathrm{O}(K)\) so that the answer can be computed in a total of \(\mathrm{O}(K B \log N)\) time, where \(B=10\) is the radix, but still, this solution will result in TLE.

In order to decrease the number of states further, we focus on the property of product \(p\). Since \(p\) is either \(0\) or a product of \(1,2,\dots,9\), and integers \(1, \ldots, 9\) has only \(2, 3, 5, 7\) as prime factors, the product \(p\) of digits of an integer not exceeding \(N\) can be expressed as

\[p=0\text{ or }p=2^a \cdot 3^b \cdot 5^c \cdot 7^d.\]

By this fact, we can decrease the number of states from \(O(K)\). Since the states of \(p\) greater than \(K\) does not need to be stored, one have the inequality \(p = 2^a \cdot 3^b \cdot 5^c \cdot 7^d \leq K\). The order of the number of combinations \((a, b, c, d)\) satisfying the condition can be estimated by the necessary condition expressed in the following inequality

\[ 0 \leq a \leq \log_2 K,\ 0 \leq b \leq \log_3 K ,\ 0 \leq c \leq \log_5 K,\ 0 \leq d \leq \log_7 K, \]

namely the number of states is at most \(\mathrm{O}(\log_2 K \log_3 K \log_5 K \log_7 K) = \mathrm{O}( (\log K)^4 )\). (Actually \(a+b+c+d\) is bounded by \(\mathrm{O}(\log K)\), so it has a constant around \(\frac{1}{4!}\).)

Therefore, we have seen that the number of states required for the problem is \(\mathrm{O}((\log K) ^ 4)\). Then, we can implement a DP described in section 1 of complexity \(\mathrm{O}(B (\log K) ^ 4 \log N)\) by storing only the necessary values. The DP values can be managed easily with associated arrays (like std::unordered_map in C++ or defaultdict in Python).

Therefore, the problem has been solved in a total of \(\mathrm{O}(B (\log K) ^ 4 \log N)\) where \(B=10\). The following is an AC code.

from collections import defaultdict

N, _K = input().split()
K = int(_K)
INF = K + 1

dp = defaultdict(int)
eq_prod = 1

for i in range(len(N)):
  digit = ord(N[i]) - ord('0')
  nxt = defaultdict(int)

  # less -> less
  for prod, val in dp.items():
    for d in range(10):
      nxt_prod = min(INF, prod * d)
      nxt[nxt_prod] += val

  # equal -> less
  for d in range(digit):
    if i == 0 and d == 0:
      continue
    nxt_prod = min(INF, eq_prod * d)
    nxt[nxt_prod] += 1

  # equal -> equal
  eq_prod = min(INF, eq_prod * digit)

  # 1 ... 9
  if i != 0:
    for d in range(1, 10):
      nxt_prod = min(INF, d)
      nxt[nxt_prod] += 1

  dp = nxt

answer = 0

# less
for prod, val in dp.items():
  if prod <= K:
    answer += val

# equal
if eq_prod <= K:
  answer += 1

print(answer)