Overview

This problem asks us to count integers from \(1\) to \(N\) whose digit product (the product of all digits) is non-zero and a multiple of \(M\). Since \(N\) can be as large as \(10^{18}\), we use Digit DP to efficiently perform the counting.

Analysis

Problems with a Naive Approach

Since \(N\) can be up to \(10^{18}\), brute-force checking every number from \(1\) to \(N\) is far too slow (TLE).

Key Observations

1. Structure suitable for Digit DP: The form “count integers up to \(N\) that satisfy certain per-digit conditions” is a classic application of Digit DP.

2. Numbers containing 0 can be ignored: Once a digit \(0\) appears, the digit product becomes \(0\), which fails the condition. Therefore, except for leading zeros, all branches that use the digit \(0\) can be ignored.

3. No need to store the digit product directly: The digit product itself can become extremely large, but since we only care about whether it is a multiple of \(M\), it suffices to keep only \(\text{digit product} \mod M\) as a state.

Algorithm

We construct a Digit DP with the following states:

• pos: The current digit position being considered (from the most significant digit: \(0, 1, \ldots, n-1\))
• tight: Whether all digits chosen so far match \(N\) exactly (if True, the current digit has an upper bound)
• started: Whether we have passed the leading zeros and the actual number has begun
• prod_mod: The remainder of the digit product so far divided by \(M\)

Transitions: At each digit, we choose a digit from \(0\) to \(9\) (up to the upper bound if tight).

• If the number has not started yet (started = False):

  • Choose \(d = 0\): The number still hasn’t started (leading zero)
  • Choose \(d \geq 1\): The number starts, and prod_mod = d \mod M

• If the number has already started (started = True):

  • Choose \(d = 0\): The digit product becomes \(0\), so this branch is not counted (continue)
  • Choose \(d \geq 1\): Update prod_mod to (prod_mod × d) mod M

Termination condition: When all digits have been decided, if started = True and prod_mod = 0, then the digit product is a multiple of \(M\), so we add \(+1\) to the count.

Concrete Example

For \(N = 123, M = 6\), for example, \(26\) has digit product \(2 \times 6 = 12\), which is a multiple of \(6\) → counted. \(205\) has digit product \(0\) → not counted.

Complexity

• Time complexity: \(O(n \times 2 \times 2 \times M \times 10) = O(n \cdot M)\)
  • \(n = \lfloor \log_{10} N \rfloor + 1 \leq 19\) (number of digits)
  • The number of states is approximately \(19 \times 2 \times 2 \times 500 = 38{,}000\), with at most \(10\) transitions per state
  • Approximately \(380{,}000\) computations in total
• Space complexity: \(O(n \cdot M)\) (size of the memoization table)

Implementation Notes

• Recursive memoization with lru_cache: In Python, using @lru_cache allows for concise memoized recursion over states.

• Pruning when \(d = 0\): When started = True and \(d = 0\) is chosen, the digit product is guaranteed to be \(0\), so we continue without recursing. This significantly reduces unnecessary state transitions.

• Propagation of the tight flag: The upper bound constraint carries over to the next digit only when the same digit as \(N\) was chosen at the current position. Otherwise, digits \(0\) through \(9\) can be chosen freely.

  Source Code

import sys
from functools import lru_cache

def solve():
    N, M = map(int, input().split())
    
    digits = []
    tmp = N
    while tmp > 0:
        digits.append(tmp % 10)
        tmp //= 10
    digits.reverse()
    n = len(digits)
    
    # Digit DP
    # State: position, tight (whether we're still bounded by N), started (whether we've placed a non-zero digit), 
    #        product mod M, has_zero (whether any digit 0 has been placed after starting)
    # 
    # Actually, we need to track whether the product contains a zero digit.
    # If any digit after we start is 0, the entire product is 0, so we should not count it.
    # So we track: has_zero flag
    # And product mod M of non-zero digits seen so far (but if has_zero, we skip anyway)
    #
    # Wait, if has_zero is true, product is 0, so we never count it. So we can just skip those branches.
    # We only need to track product mod M for numbers where no digit is 0 (after leading zeros are handled).
    
    # States: pos, tight, started, prod_mod
    # If not started, prod_mod is irrelevant (use 0 or something)
    # Once started, all digits must be 1-9 (no zero allowed, since zero makes product 0)
    # prod_mod tracks product mod M
    
    # dp[pos][tight][started][prod_mod] = count
    # pos: 0..n
    # tight: 0 or 1
    # started: 0 or 1
    # prod_mod: 0..M-1
    
    @lru_cache(maxsize=None)
    def dp(pos, tight, started, prod_mod):
        if pos == n:
            if started and prod_mod == 0:
                return 1
            return 0
        
        limit = digits[pos] if tight else 9
        result = 0
        
        for d in range(0, limit + 1):
            new_tight = tight and (d == limit)
            
            if not started:
                if d == 0:
                    # Still haven't started
                    result += dp(pos + 1, new_tight, False, 0)
                else:
                    # Start with digit d (d >= 1)
                    result += dp(pos + 1, new_tight, True, d % M)
            else:
                # Already started
                if d == 0:
                    # Placing a 0 makes the product 0, so this number won't count
                    # We can skip entirely (no need to recurse, all paths lead to product=0)
                    # But we still need to count 0 for these... no, we don't count them.
                    # So just skip.
                    # Actually we need to NOT count them, so we just don't add anything.
                    # But there could be multiple digits remaining. All those numbers have product 0.
                    continue
                else:
                    new_prod = (prod_mod * d) % M
                    result += dp(pos + 1, new_tight, True, new_prod)
        
        return result
    
    print(dp(0, True, False, 0))

solve()

---

This editorial was generated by claude4.6opus-thinking.