Overview

This problem asks us to count the integers from \(1\) to \(N\) that do not contain the digit \(0\) in any position and whose product of all digits (digit product) is a multiple of \(M\).

Since \(N\) can be as large as \(10^{18}\), a method that checks each number from \(1\) to \(N\) sequentially cannot meet the time limit. To efficiently count “the number of integers at most \(N\) satisfying certain digit-related conditions,” we use digit DP (digit dynamic programming).

---

Analysis

1. Naive Approach and Its Limitations

The naive approach (brute force) of looping from \(1\) to \(N\), computing the digit product of each number, and checking divisibility by \(M\) has a time complexity of \(O(N \log N)\). Since \(N \le 10^{18}\), this method will certainly result in a Time Limit Exceeded (TLE) verdict.

2. Applying Digit DP and Designing the “State”

We consider a “digit DP” that determines digits from the most significant to the least significant. If we try to keep the digit product itself as the DP state, the product can take up to \(9^{18} \approx 1.5 \times 10^{17}\) different values, causing a state explosion.

However, all we need to know is “whether the final digit product is a multiple of \(M\) (i.e., whether the remainder when divided by \(M\) is \(0\))”. By the properties of modular arithmetic, as long as we know the remainder of the intermediate product, we can correctly compute the remainder after multiplying by the next digit. Specifically, $\(\text{(new product)} \pmod M = ((\text{product so far} \pmod M) \times d) \pmod M\)$ holds.

Therefore, the DP state only needs to store “the remainder of the digit product divided by \(M\)”, not the digit product itself. This limits the number of states to \(M\) values (from \(0\) to \(M-1\)).

3. Organizing the Conditions

• Digit product is not zero: We cannot choose \(0\) for any digit. Therefore, the usable digits are always only \(1\) through \(9\).
• At most \(N\): Numbers with fewer digits than \(N\)’s digit count \(L\) are certainly at most \(N\). For numbers with exactly \(L\) digits, we need to track “whether it has been determined to be less than \(N\)” as we decide digits from the top.

---

Algorithm

In this algorithm, we divide the numbers to search into the following two groups and count them.

Part 1: Numbers with fewer than \(L\) digits (from \(1\) digit to \(L-1\) digits)

These numbers are certainly less than \(N\), so we can freely place any digit from \(1\) to \(9\) in each position.

• DP Table Definition: current_dp[rem]: The count of numbers of the current length whose digit product has remainder rem when divided by \(M\).
• Initial State: For length \(0\) (product is \(1\)), set current_dp[1 % M] = 1 and all others to \(0\).
• Transition: While increasing the length from \(1\) to \(L-1\), multiply by the next digit \(d \in \{1, 2, \dots, 9\}\). $\(\text{next\_dp}[(rem \times d) \pmod M] \leftarrow \text{next\_dp}[(rem \times d) \pmod M] + \text{current\_dp}[rem]\)$
• Adding to the Answer: At each length, add the count with remainder \(0\) (next_dp[0]) to the answer ans.

Part 2: Numbers with exactly \(L\) digits (same number of digits as \(N\)) that are at most \(N\)

We determine digits from the most significant position onward. Similar to standard digit DP, we maintain the following two states.

• DP Table Definition:
  • dp_tight[rem]: The count of numbers whose determined prefix matches \(N\)’s prefix exactly, with remainder rem (always \(0\) or \(1\)).
  • dp_less[rem]: The count of numbers that have been determined to be less than \(N\) at some earlier digit, with remainder rem.
• Transition: Let \(limit\) be the digit of \(N\) at position \(j\).
  1. Transitions from dp_tight:
     • When choosing digit \(d\) for the next position:

          - If $1 \le d < limit$: It is now determined to be less than $N$, so transition to `next_less`.
          - If $d = limit$: It still matches $N$, so transition to `next_tight` (only if $limit \ge 1$).
       

  2. Transitions from dp_less:
     • Since it is already determined to be less than \(N\), the next digit \(d\) can be any of \(1 \le d \le 9\), and all transitions go to next_less.
• Adding to the Answer: After determining all \(L\) digits, add dp_tight[0] + dp_less[0] to ans.

---

Complexity

Let \(L\) be the number of digits in the decimal representation of \(N\) (\(L \le 18\)).

Time Complexity: \(O(L \cdot M)\)

• In both Part 1 and Part 2, within the loop over digit count \(L\), we iterate over the number of remainders \(rem\) which is \(M\), and the number of digit choices \(d\) which is \(9\) (a nested loop).
• The total number of transitions is at most about \(2 \times L \times M \times 9\).
• When \(L \le 18, M \le 500\), the worst case is approximately \(1.6 \times 10^5\) operations, which runs sufficiently fast (a few milliseconds) within the time limit (2.0 seconds).

Space Complexity: \(O(M)\)

• The DP tables consist of only a few arrays of size \(M\).
• The required memory is extremely small, with space complexity of \(O(M)\), making it very memory-efficient.

---

Implementation Notes

1. Handling the constraint that \(0\) cannot be used: In the loop for each digit, by setting the lower bound to \(1\) (e.g., range(1, 10) or range(1, limit)), transitions using the digit \(0\) are naturally excluded.

2. tight transition when \(limit = 0\): When a certain digit of \(N\) is \(0\) (e.g., the second digit of \(N = 205\)), transitioning from dp_tight with \(d = limit = 0\) is not allowed (since \(0\) cannot be used). The conditional branch if limit >= 1: in the code prevents this invalid transition.

3. Initial remainder value: The initial value for multiplication is \(1\). Therefore, during DP initialization, we assign the initial value \(1\) to the position 1 % M. To handle cases such as \(M = 1\), using 1 % M instead of directly 1 is an important implementation detail for correctness.

   Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N_str = data[0]
    M = int(data[1])

    L = len(N_str)
    N_digits = [int(c) for c in N_str]

    # 長さ 1 から L-1 までの数について
    ans = 0
    current_dp = [0] * M
    current_dp[1 % M] = 1

    for length in range(1, L):
        next_dp = [0] * M
        for rem in range(M):
            count = current_dp[rem]
            if count == 0:
                continue
            for d in range(1, 10):
                next_dp[(rem * d) % M] += count
        ans += next_dp[0]
        current_dp = next_dp

    # 長さ L の数で、N 以下のもの
    dp_tight = [0] * M
    dp_tight[1 % M] = 1
    dp_less = [0] * M

    for j in range(L):
        limit = N_digits[j]
        next_tight = [0] * M
        next_less = [0] * M

        # dp_tight からの遷移
        for rem in range(M):
            count = dp_tight[rem]
            if count == 0:
                continue
            # 1 <= d < limit
            for d in range(1, limit):
                next_less[(rem * d) % M] += count
            # d = limit
            if limit >= 1:
                next_tight[(rem * limit) % M] += count

        # dp_less からの遷移
        for rem in range(M):
            count = dp_less[rem]
            if count == 0:
                continue
            for d in range(1, 10):
                next_less[(rem * d) % M] += count

        dp_tight = next_tight
        dp_less = next_less

    ans += dp_tight[0] + dp_less[0]

    print(ans)


if __name__ == "__main__":
    solve()

---

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