Overview

This problem asks us to count the integers in a given range \([L, R]\) whose digit product equals \(K\). We solve it using digit DP (dynamic programming on digits), reducing it to answering queries over the range \([1, X]\).

Analysis

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

As a classic technique, the count of integers satisfying a condition in the interval \([L, R]\) can be obtained by subtracting the count in \([1, L-1]\) from the count in \([1, R]\). Therefore, if we implement a function \(\text{solve}(X)\) that counts integers from \(1\) to \(X\) satisfying \(f(n) = K\), the answer is \(\text{solve}(R) - \text{solve}(L-1)\).

2. Case \(K = 0\)

\(f(n) = 0\) occurs when at least one digit is \(0\). This can be computed by subtracting “the count of numbers where all digits are from \(1\) to \(9\)” from the total. The count of integers from \(1\) to \(X\) where all digits are from \(1\) to \(9\) (i.e., \(0\) is never used) can be found with a simple digit DP. Since the total number of integers from \(1\) to \(X\) is \(X\), the count of numbers with \(f(n) = 0\) is \(X - (\text{count of numbers not containing } 0)\).

3. Case \(K > 0\)

When \(K > 0\), no digit can be \(0\) (since including \(0\) would make the product \(0\)). Thus, each digit must be one of \(1\) through \(9\). In this case, the prime factors of \(K\) (the product of the digits) must be among \(2, 3, 5, 7\). If \(K\) has any other prime factor (such as \(11\) or \(13\)), no \(n\) with \(f(n) = K\) exists, so the answer is \(0\).

When \(K\) has only \(2, 3, 5, 7\) as prime factors, during the process of determining each digit, “the product of the digits determined so far” must be a divisor of \(K\). Also, the product that needs to be achieved by the remaining digits is also a divisor of \(K\). For \(K \le 10^{18}\), the number of divisors of \(K\) whose only prime factors are \(2, 3, 5, 7\) is at most around \(60{,}000\), which is very small. Using this property, we can perform a digit DP where the state includes “the remaining required product (as an index into the list of divisors of \(K\))”.

Algorithm

1. Enumerating Divisors of \(K\) and Building the Transition Table

First, factorize \(K\) into the primes \(2, 3, 5, 7\). If any other prime factor exists, output \(0\) and terminate. Enumerate all divisors of \(K\) and sort them in ascending order. For each divisor \(v\), for each digit \(1 \le d \le 9\), if \(v\) is divisible by \(d\) and the quotient \(v/d\) is also a divisor of \(K\), precompute the transition destination (the index of the divisor) in a next_div table.

2. Digit DP Design

For integers from \(1\) to \(X\), define the state after determining up to the \(i\)-th digit from the top as follows: dfs(idx, is_less, is_started, div_idx) - idx: The current digit position (from \(0\) to \(N-1\), where \(N\) is the number of digits of \(X\)) - is_less: Whether it is confirmed to be less than \(X\) (true / false) - is_started: Whether we have started placing digits \(\ge 1\) (for handling leading zeros, true / false) - div_idx: The index of the divisor of \(K\) representing the product that still needs to be achieved by the remaining digits

Transitions:

1. If digit placement has not started yet (!is_started): We can skip the current digit and proceed to the next one (effectively ignoring leading zeros). Transition to dfs(idx + 1, true, false, div_idx).
2. Placing a digit \(d \in [1, limit]\): Here, \(limit\) is \(9\) if is_less is true, or the idx-th digit of \(X\) if false. If the current required product \(divs[div\_idx]\) is divisible by \(d\), the next state is dfs(idx + 1, is_less || (d < limit), true, nxt_div_idx), where nxt_div_idx is the index of \(divs[div\_idx] / d\).

Base Case:

When idx == N (all digits have been determined), return \(1\) if is_started is true and divs[div_idx] == 1 (the entire required product has been achieved); otherwise return \(0\).

By implementing this with memoized recursion, we can compute the answer efficiently.

Complexity

• Time complexity: \(O(N \times D + D \log D)\) Let \(D\) be the number of divisors of \(K\). For \(K \le 10^{18}\), \(D \le 60{,}000\). The number of states in the digit DP is \(O(N \times D)\) (where \(N = \log_{10} R \le 18\)). Since there are \(9\) transitions (digits \(1\) through \(9\)) from each state, the total complexity of the DP is \(O(N \times D)\). Enumerating divisors and building the transition table also take \(O(D \log D)\), which is sufficiently fast. Overall, this comfortably fits within the time limit.

• Space complexity: \(O(N \times D)\) The memoization array has size \(O(N \times D)\). The divisor list and transition table are also of size \(O(D)\), and the total memory usage is on the order of a few megabytes.

Implementation Notes

• Fast divisor lookup: If we perform a binary search (std::lower_bound) every time we need to find the index of a divisor during DP transitions, it becomes slow. By precomputing the transition destinations as a table next_div[div_idx][d], we speed up the main DP computation.

• Flattening the memoization array to 1D: Multi-dimensional std::vector incurs significant overhead from dynamic allocation. By mapping the state to a 1D index and using a 1D array, we improve both memory efficiency and execution speed.

  Source Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// f(n) = 0 となるものの個数を求めるための、すべての桁が 1-9 であるものの個数
long long solve_h(long long X) {
    if (X <= 0) return 0;
    string S = to_string(X);
    int n = S.size();
    vector memo(n, vector(2, vector<long long>(2, -1)));
    auto dfs = [&](auto& self, int idx, bool is_less, bool is_started) -> long long {
        if (idx == n) {
            return is_started ? 1 : 0;
        }
        if (memo[idx][is_less][is_started] != -1) {
            return memo[idx][is_less][is_started];
        }
        long long res = 0;
        if (!is_started) {
            res += self(self, idx + 1, true, false);
        }
        int limit = is_less ? 9 : (S[idx] - '0');
        for (int d = 1; d <= limit; ++d) {
            res += self(self, idx + 1, is_less || (d < limit), true);
        }
        return memo[idx][is_less][is_started] = res;
    };
    return dfs(dfs, 0, false, false);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long L, R, K;
    if (!(cin >> L >> R >> K)) return 0;

    if (K == 0) {
        long long ans = (R - solve_h(R)) - ((L - 1) - solve_h(L - 1));
        cout << ans << "\n";
        return 0;
    }

    // K > 0 の場合
    // 素因数分解
    long long temp = K;
    int A = 0, B = 0, C = 0, D = 0;
    while (temp % 2 == 0) { temp /= 2; A++; }
    while (temp % 3 == 0) { temp /= 3; B++; }
    while (temp % 5 == 0) { temp /= 5; C++; }
    while (temp % 7 == 0) { temp /= 7; D++; }

    if (temp > 1) {
        cout << 0 << "\n";
        return 0;
    }

    // 約数の列挙
    vector<long long> divs;
    long long p2 = 1;
    for (int a = 0; a <= A; ++a) {
        long long p3 = p2;
        for (int b = 0; b <= B; ++b) {
            long long p5 = p3;
            for (int c = 0; c <= C; ++c) {
                long long p7 = p5;
                for (int d = 0; d <= D; ++d) {
                    divs.push_back(p7);
                    if (D - d > 0 && p7 > K / 7) break;
                    p7 *= 7;
                }
                if (C - c > 0 && p5 > K / 5) break;
                p5 *= 5;
            }
            if (B - b > 0 && p3 > K / 3) break;
            p3 *= 3;
        }
        if (A - a > 0 && p2 > K / 2) break;
        p2 *= 2;
    }
    sort(divs.begin(), divs.end());
    int num_divs = divs.size();

    vector<vector<int>> next_div(num_divs, vector<int>(10, -1));
    for (int i = 0; i < num_divs; ++i) {
        long long val = divs[i];
        for (int d = 1; d <= 9; ++d) {
            if (val % d == 0) {
                long long target = val / d;
                auto it = lower_bound(divs.begin(), divs.end(), target);
                if (it != divs.end() && *it == target) {
                    next_div[i][d] = distance(divs.begin(), it);
                }
            }
        }
    }

    auto solve = [&](long long X) -> long long {
        if (X <= 0) return 0;
        string S = to_string(X);
        int n = S.size();
        int state_size = n * 4 * num_divs;
        vector<long long> memo(state_size, -1);

        auto get_memo_idx = [&](int idx, bool is_less, bool is_started, int div_idx) {
            return ((idx * 2 + is_less) * 2 + is_started) * num_divs + div_idx;
        };

        auto dfs = [&](auto& self, int idx, bool is_less, bool is_started, int div_idx) -> long long {
            if (idx == n) {
                if (is_started && divs[div_idx] == 1) return 1;
                return 0;
            }
            int memo_idx = get_memo_idx(idx, is_less, is_started, div_idx);
            if (memo[memo_idx] != -1) {
                return memo[memo_idx];
            }

            long long res = 0;
            if (!is_started) {
                res += self(self, idx + 1, true, false, div_idx);
            }

            int limit = is_less ? 9 : (S[idx] - '0');
            for (int d = 1; d <= limit; ++d) {
                int nxt_div_idx = next_div[div_idx][d];
                if (nxt_div_idx != -1) {
                    res += self(self, idx + 1, is_less || (d < limit), true, nxt_div_idx);
                }
            }
            return memo[memo_idx] = res;
        };

        return dfs(dfs, 0, false, false, num_divs - 1);
    };

    long long ans = solve(R) - solve(L - 1);
    cout << ans << "\n";

    return 0;
}

---

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