概要

\(L\) 以上 \(R\) 以下の整数 \(n\) のうち、各桁の数字の積 \(f(n)\) が \(K\) に等しいものの個数を、桁DPを用いて求める問題です。

考察

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

\(R\) が最大 \(10^{18}\) なので、すべての整数を一つずつ調べることは不可能です（TLE）。

重要な観察

1. 範囲の分割: \([L, R]\) の答えは「\([1, R]\) での答え」−「\([1, L-1]\) での答え」と分解できます。これにより「\(N\) 以下の整数で条件を満たすものの個数」を求める問題に帰着します。

2. \(K = 0\) の場合: \(f(n) = 0\) ⇔ \(n\) のいずれかの桁に \(0\) が含まれる。これは「\(0\) を含む数の個数」を数えるシンプルな桁DPで解けます。

3. \(K > 0\) の場合: 各桁は \(1\)〜\(9\) のいずれかでなければなりません（\(0\) があると積が \(0\) になるため）。桁の積は \(1\)〜\(9\) の数の積なので、\(K\) の素因数は \(2, 3, 5, 7\) のみでなければなりません。それ以外の素因数を持つなら答えは即座に \(0\) です。

4. 積の状態数が少ない: \(K\) の約数のみが「途中経過の積」として現れ得ます。\(K = 2^a \times 3^b \times 5^c \times 7^d\)（ただし \(K \leq 10^{18}\)）の約数の個数は高々数百〜数千程度であり、桁DPの状態として管理可能です。

アルゴリズム

桁DP

上界 \(N\) を十進表記した桁列 \(d_0 d_1 \ldots d_{n-1}\) に対して、以下の状態でメモ化再帰を行います。

• pos: 現在見ている桁の位置
• tight: これまで選んだ桁が \(N\) の上位桁とぴったり一致しているか（上界制約）
• started: 先頭のゼロ埋め期間を過ぎて数が始まっているか
• \(K = 0\) の場合: has_zero — 既に \(0\) の桁が現れたか
• \(K > 0\) の場合: prod_idx — 現在の桁の積を、\(K\) の約数リストのインデックスで管理

\(K > 0\) での枝刈り

各桁で数字 \(d\) を選ぶとき、次の条件で枝刈りします： - \(d = 0\) なら積が \(0\) になるのでスキップ - 新しい積 = (現在の積) \(\times d\) が \(K\) を超えるならスキップ - 新しい積が \(K\) の約数でないならスキップ（\(K\) に到達不可能）

計算量

\(N\) の桁数を \(D\)（最大 \(19\)）、\(K\) の約数の個数を \(M\) とします。

• \(K = 0\) の場合:

  • 時間計算量: \(O(D \times 2 \times 2 \times 2 \times 10) = O(D)\)
  • 空間計算量: \(O(D)\)

• \(K > 0\) の場合:

  • 時間計算量: \(O(D \times 2 \times 2 \times M \times 10)\)
  • 空間計算量: \(O(D \times M)\)
  • \(K \leq 10^{18}\) かつ素因数が \(2, 3, 5, 7\) のみのとき、\(M\) は最大でも数千程度（例えば \(2^{59}\) で約数 \(60\) 個、混合でもそれほど増えない）

実装のポイント

• count(R) - count(L-1) パターン: 桁DPの典型テクニックで、範囲の問題を上界だけの問題に変換します。

• started フラグ: 先頭ゼロ（例えば “007” のような表現）を正しく扱うために必要です。\(K > 0\) のとき、数が始まる前の \(0\) は「桁に含まれる \(0\)」ではないことに注意。

• 約数のインデックス化: 積の値そのものではなく、\(K\) の約数リスト中のインデックスで状態を管理することで、メモ化を効率的に行います。

• 素因数チェック: \(K > 0\) で \(K\) が \(2, 3, 5, 7\) 以外の素因数を持つ場合、どんな桁の組み合わせでも \(K\) を作れないため即座に \(0\) を出力できます。

  ソースコード

import sys
from functools import lru_cache

def solve():
    L, R, K = map(int, input().split())
    
    # Count numbers in [1, N] with digit product == K
    # Answer = count(R) - count(L-1)
    
    # Special case: K = 0
    # f(n) = 0 iff n contains digit 0
    # Count of n in [1, N] with f(n)=0 = count of n in [1,N] with at least one 0 digit
    
    # For K >= 1, digits are all 1-9
    # The digit product is a product of digits from 1-9
    # So K must factor into primes 2,3,5,7 only
    
    # We use digit DP. For each number up to N, we track the running product.
    # But the product can be huge. We need to be smart.
    
    # Key insight: if K=0, we count numbers with at least one zero digit.
    # If K>0, K must be expressible as product of digits 1-9, meaning
    # K = 2^a * 3^b * 5^c * 7^d for some non-negative a,b,c,d.
    # Also the product of digits 1-9 for an 18-digit number is at most 9^18 ~ 1.5 * 10^17 < 10^18.
    
    # For K != 0: We do digit DP tracking the current product.
    # The product at any point is a divisor of K (if we only consider paths that can reach K).
    # We can prune: current product must divide K, and remaining digits must be able to 
    # multiply to reach K/current_product.
    
    # Let's use memoization with (position, product_so_far, tight, started)
    # product_so_far can be at most K, and must divide K. 
    # Number of divisors of K where K <= 10^18 can be large but since K = 2^a*3^b*5^c*7^d,
    # the number of divisors is manageable (at most ~60*40*27*22 but K<=10^18 limits this).
    
    # Actually for K that has prime factors other than 2,3,5,7, and K>0, answer is 0.
    
    if K == 0:
        # Count numbers in [L, R] that contain at least one '0' digit
        def count_with_zero(N):
            if N <= 0:
                return 0
            digits = list(map(int, str(N)))
            n = len(digits)
            
            @lru_cache(maxsize=None)
            def dp(pos, tight, started, has_zero):
                if pos == n:
                    if not started:
                        return 0
                    return 1 if has_zero else 0
                limit = digits[pos] if tight else 9
                res = 0
                for d in range(0, limit + 1):
                    new_tight = tight and (d == limit)
                    new_started = started or (d != 0)
                    new_has_zero = has_zero or (started and d == 0)
                    res += dp(pos + 1, new_tight, new_started, new_has_zero)
                return res
            
            result = dp(0, True, False, False)
            dp.cache_clear()
            return result
        
        print(count_with_zero(R) - count_with_zero(L - 1))
    else:
        # Check if K can be expressed as product of digits 1-9
        # K must only have prime factors 2, 3, 5, 7
        tmp = K
        for p in [2, 3, 5, 7]:
            while tmp % p == 0:
                tmp //= p
        if tmp != 1:
            print(0)
            return
        
        # Get all divisors of K
        def get_divisors(K):
            divs = [1]
            for p in [2, 3, 5, 7]:
                new_divs = []
                pk = 1
                while pk <= K:
                    for d in divs:
                        if d * pk <= K and K % (d * pk) == 0:
                            new_divs.append(d * pk)
                    pk *= p
                divs = list(set(new_divs))
            return sorted(divs)
        
        divisors = get_divisors(K)
        div_index = {d: i for i, d in enumerate(divisors)}
        nd = len(divisors)
        
        def count_eq_K(N):
            if N <= 0:
                return 0
            digits = list(map(int, str(N)))
            n = len(digits)
            
            @lru_cache(maxsize=None)
            def dp(pos, tight, started, prod_idx):
                if pos == n:
                    if not started:
                        return 0
                    return 1 if divisors[prod_idx] == K else 0
                limit = digits[pos] if tight else 9
                res = 0
                for d in range(0, limit + 1):
                    new_tight = tight and (d == limit)
                    if not started and d == 0:
                        res += dp(pos + 1, new_tight, False, 0)
                    else:
                        if d == 0:
                            continue  # product becomes 0, can't reach K>0
                        new_prod = divisors[prod_idx] * d if started else d
                        if new_prod > K or K % new_prod != 0:
                            continue
                        if new_prod not in div_index:
                            continue
                        res += dp(pos + 1, new_tight, True, div_index[new_prod])
                return res
            
            result = dp(0, True, False, 0)
            dp.cache_clear()
            return result
        
        print(count_eq_K(R) - count_eq_K(L - 1))

solve()

---

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