概要

\(1\) 以上 \(N\) 以下の整数のうち、各桁の数字の積（桁積）が \(0\) でなく、かつ \(M\) の倍数であるものの個数を求める問題です。\(N\) が最大 \(10^{18}\) と非常に大きいため、桁DP（Digit DP）を用いて効率的に数え上げます。

考察

素朴なアプローチの問題点

\(N\) が最大 \(10^{18}\) なので、\(1\) から \(N\) まで全数探索すると到底間に合いません（TLE）。

重要な気づき

1. 桁DP が使える構造: 「\(N\) 以下の整数で、ある桁ごとの条件を満たすものを数える」という形は、桁DPの典型です。

2. 0 を含む数は無視できる: 一度でも数字 \(0\) が現れると桁積は \(0\) になり、条件を満たしません。したがって、先頭を除いて数字 \(0\) を使った分岐は全て無視できます。

3. 桁積を直接持つ必要はない: 桁積そのものは非常に大きくなり得ますが、\(M\) の倍数かどうかだけが重要なので、\(\text{桁積} \mod M\) のみを状態として持てば十分です。

アルゴリズム

桁DP を以下の状態で構築します：

• pos: 現在見ている桁の位置（上の桁から順に \(0, 1, \ldots, n-1\)）
• tight: 上の桁まで \(N\) と一致しているか（True なら現在の桁に上限あり）
• started: 先頭の \(0\)（リーディングゼロ）を抜けて、実際に数字が始まったか
• prod_mod: ここまでの桁積を \(M\) で割った余り

遷移: 各桁で \(0\) から \(9\)（tight なら上限まで）の数字を選びます。

• まだ始まっていない場合 (started = False):

  • \(d = 0\) を選ぶ：まだ始まらない（リーディングゼロ）
  • \(d \geq 1\) を選ぶ：数が始まり、prod_mod = d \mod M となる

• 既に始まっている場合 (started = True):

  • \(d = 0\) を選ぶ：桁積が \(0\) になるので、この分岐は数えない（continue）
  • \(d \geq 1\) を選ぶ：prod_mod を (prod_mod × d) mod M に更新

終了条件: 全桁を決めた時点で started = True かつ prod_mod = 0 なら、桁積が \(M\) の倍数なのでカウント \(+1\)。

具体例

\(N = 123, M = 6\) の場合、例えば \(26\) は桁積 \(2 \times 6 = 12\) で \(6\) の倍数 → カウント。\(205\) は桁積 \(0\) → カウントしない。

計算量

• 時間計算量: \(O(n \times 2 \times 2 \times M \times 10) = O(n \cdot M)\)
  • \(n = \lfloor \log_{10} N \rfloor + 1 \leq 19\)（桁数）
  • 状態数は \(19 \times 2 \times 2 \times 500 = 38{,}000\) 程度、各状態で最大 \(10\) 通り遷移
  • 全体で約 \(380{,}000\) 回の計算
• 空間計算量: \(O(n \cdot M)\)（メモ化テーブルのサイズ）

実装のポイント

• lru_cache による再帰メモ化: Python では @lru_cache を使うことで、状態のメモ化を簡潔に書けます。

• \(d = 0\) の枝刈り: started = True の状態で \(d = 0\) を選ぶと桁積が確定で \(0\) になるため、再帰せずに continue します。これにより無駄な状態遷移を大幅に削減できます。

• tight フラグの伝播: 上の桁で \(N\) と同じ数字を選んだ場合のみ、次の桁にも上限制約が伝わります。それ以外では \(0\)〜\(9\) を自由に選べます。

  ソースコード

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()

この解説は claude4.6opus-thinking によって生成されました。