Overview

This problem asks us to find the count of integers within a given range \([L, R]\) such that the product of their digits equals \(K\).

Since the number of digits can be up to \(18\) digits (\(10^{18}\)), which is extremely large, we cannot simply loop from \(L\) to \(R\) and check each number. For problems like “count integers within a range that satisfy a condition related to their digits,” the technique of Digit DP (Digit Dynamic Programming) is effective.

---

Analysis

1. Reformulating the Range \([L, R]\)

Directly computing “the count of numbers between \(L\) and \(R\) inclusive” is difficult, so we use the idea of prefix sums. Define \(g(N)\) as “the count of integers from \(1\) to \(N\) inclusive whose digit product equals \(K\).” Then the answer can be expressed as:

\[g(R) - g(L - 1)\]

This simplifies the problem to only considering an upper bound \(N\).

2. Case Analysis Based on the Value of \(K\)

We consider the conditions under which the digit product \(f(n)\) equals \(K\). The approach differs depending on the value of \(K\).

Pattern A: When \(K = 0\)

A product of \(0\) means “at least one digit contains \(0\).” Rather than counting this directly, it is easier to consider the complement (the opposite pattern). The total count of integers from \(1\) to \(N\) inclusive is \(N\). By subtracting “the count of integers that never contain \(0\)” from this, we can find the count where \(K=0\).

Pattern B: When \(K > 0\)

For the product to equal \(K\), no digit can be \(0\) (since having a \(0\) would make the product \(0\)). Therefore, the digits that can be chosen are \(1\) through \(9\). Additionally, the prime factors of digits (\(1 \sim 9\)) are only \(2, 3, 5, 7\). Thus, if \(K\) has a prime factor other than \(2, 3, 5, 7\), it is impossible to make the digit product equal \(K\) regardless of how the digits are chosen. In this case, the answer is immediately \(0\).

When \(K\) is composed only of the primes \(2, 3, 5, 7\), we determine digits from the top and manage the remaining required product by dividing the current target value \(val\) (initially \(K\)) by the chosen digit \(d\) at each position.

---

Algorithm

We implement the digit DP using memoized recursion (DFS).

State Definition

We define the recursive function dfs(idx, is_less, is_started, val).

• idx: The index of the digit currently being determined (the idx-th digit from the top).
• is_less: Whether the number being constructed is already confirmed to be less than \(N\) (less-than flag).
  • If False, the upper limit of the digit at this position is the corresponding digit of \(N\).
  • If True, any digit from \(0 \sim 9\) can be chosen at this position.
• is_started: Whether we have already started placing digits of value \(1\) or greater (leading zero prevention flag).
  • For example, when considering the number \(25\) with \(N=123\), we want to treat the first digit from the top as “no digit (\(0\)).” While placing these “zeros for adjusting the effective number of digits,” we keep is_started = False and exclude them from the product calculation.
• val: The target product that must be achieved with the remaining digits.

Transitions

The transitions when choosing digit \(d\) at each position are as follows:

1. When digit determination has not yet started (is_started = False)

   • Choose \(0\): This means not placing a digit yet. is_started remains False, the target value val is unchanged, and we proceed to the next digit.
   • Choose \(1 \sim limit\): Digit determination begins here. Set is_started to True, and proceed with the next target value being val divided by \(d\) (only if val is divisible by \(d\)).

2. When digit determination has already started (is_started = True)

   • \(0\) cannot be chosen (as it would make the product \(0\)).
   • Among \(1 \sim limit\), choose a digit \(d\) that divides the current val, update the target to val // d, and proceed to the next digit.

When the last digit is reached, if is_started is True and val == 1, it means we have successfully constructed a number satisfying the condition, so we return 1; otherwise, we return 0.

---

Complexity

• Time Complexity: \(O(D \times d(K))\)

  • \(D\) is the number of digits of \(N\) (\(D \le 18\)).
  • \(d(K)\) is the number of divisors of \(K\).
  • When \(K \le 10^{18}\) and the prime factors are limited to \(2, 3, 5, 7\), the number of divisors is at most around \(5 \times 10^4\). Furthermore, the number of states actually reachable during the search is far fewer than this, so it runs very fast (on the order of tens of milliseconds) within the typical time limit (usually 2.0 seconds).

• Space Complexity: \(O(D \times d(K))\)

  • Proportional to the number of states stored in the memoization table (associative array memo). Similar to the time complexity, this is sufficiently small and easily clears the memory limit.

---

Implementation Notes

1. Increasing the Recursion Limit: In Python, the default recursion depth limit is small, so we increase it with sys.setrecursionlimit(2000).

2. Memoization Optimization: The state where is_less is False (tracing the same digits as \(N\)) is visited at most once per digit throughout the entire search. Therefore, by only recording and looking up the memoization table when is_less = True (when it is confirmed that the number is less than \(N\)), we reduce unnecessary memory usage and associative array lookup costs.

3. Fast Prime Factor Checking: When \(K > 0\), we divide by \(2, 3, 5, 7\) as many times as possible beforehand. If the remaining value is greater than \(1\), we prune by immediately returning \(0\) as it is impossible to construct such a number.

   Source Code

import sys

# 再帰上限の変更
sys.setrecursionlimit(2000)

def solve_no_zero(N):
    if N < 1:
        return 0
    S = str(N)
    D = len(S)
    memo = {}
    
    def dfs(idx, is_less, is_started):
        if idx == D:
            return 1 if is_started else 0
        
        if is_less and (idx, is_started) in memo:
            return memo[(idx, is_started)]
        
        limit = 9 if is_less else int(S[idx])
        res = 0
        
        if not is_started:
            # 0 を選ぶ
            res += dfs(idx + 1, True, False)
            # 1 ~ limit を選ぶ
            for d in range(1, limit + 1):
                res += dfs(idx + 1, is_less or (d < limit), True)
        else:
            # 0 は選べない
            for d in range(1, limit + 1):
                res += dfs(idx + 1, is_less or (d < limit), True)
                
        if is_less:
            memo[(idx, is_started)] = res
        return res
        
    return dfs(0, False, False)

def solve(N, K):
    if N < 1:
        return 0
    if K == 0:
        return N - solve_no_zero(N)
    
    # K > 0 の場合、2, 3, 5, 7 以外の素因数を持っていれば構成不可
    temp = K
    for p in (2, 3, 5, 7):
        while temp % p == 0:
            temp //= p
    if temp > 1:
        return 0
    
    S = str(N)
    D = len(S)
    memo = {}
    
    def dfs(idx, is_less, is_started, val):
        if idx == D:
            return 1 if (is_started and val == 1) else 0
        
        if is_less and (idx, is_started, val) in memo:
            return memo[(idx, is_started, val)]
        
        limit = 9 if is_less else int(S[idx])
        res = 0
        
        if not is_started:
            # 0 を選ぶ
            res += dfs(idx + 1, True, False, val)
            # 1 ~ limit を選ぶ
            for d in range(1, limit + 1):
                if val % d == 0:
                    res += dfs(idx + 1, is_less or (d < limit), True, val // d)
        else:
            # 0 は選べない（積が 0 になってしまうため）
            for d in range(1, limit + 1):
                if val % d == 0:
                    res += dfs(idx + 1, is_less or (d < limit), True, val // d)
                    
        if is_less:
            memo[(idx, is_started, val)] = res
        return res

    return dfs(0, False, False, K)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    L = int(data[0])
    R = int(data[1])
    K = int(data[2])
    
    ans = solve(R, K) - solve(L - 1, K)
    print(ans)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.5-flash-thinking.