概要

この問題は、与えられた範囲 \([L, R]\) の中から、各桁の数字の積が \(K\) になるような整数の個数を求める問題です。

桁数が最大で \(18\) 桁（\(10^{18}\)）と非常に大きいため、愚直に \(L\) から \(R\) までループを回して判定することはできません。このような「ある範囲内の整数で、桁に関する条件を満たすものの個数を数える」問題では、桁DP（桁動的計画法）という手法が有効です。

---

考察

1. 範囲 \([L, R]\) の言い換え

「\(L\) 以上 \(R\) 以下の個数」を直接求めるのは難しいため、累積和の考え方を利用します。 \(g(N)\) を「\(1\) 以上 \(N\) 以下の整数のうち、各桁の積が \(K\) になるものの個数」と定義すると、求める答えは以下の式で表せます。

\[g(R) - g(L - 1)\]

これにより、上限 \(N\) だけを考慮する問題に単純化できます。

2. \(K\) の値による場合分け

各桁の数字の積 \(f(n)\) が \(K\) になる条件を考えます。\(K\) の値によってアプローチが異なります。

パターンA: \(K = 0\) の場合

積が \(0\) になるということは、「少なくとも \(1\) つの桁に \(0\) が含まれる」ということです。 これは直接数えるよりも、余事象（逆のパターン）を考える方が簡単です。 「\(1\) 以上 \(N\) 以下のすべての整数」の個数は \(N\) 個です。ここから「\(0\) を一度も含まない整数の個数」を引くことで、 \(K=0\) となる個数を求められます。

パターンB: \(K > 0\) の場合

積が \(K\) になるためには、各桁に \(0\) を含んではいけません（\(0\) があると積が \(0\) になってしまうため）。よって、各桁で選べる数字は \(1\) から \(9\) のいずれかになります。 また、各桁の数字（\(1 \sim 9\)）の素因数は \(2, 3, 5, 7\) のみです。したがって、\(K\) が \(2, 3, 5, 7\) 以外の素因数を持つ場合、どのように桁の数字を決めても積を \(K\) にすることはできません。 この場合は即座に答えが \(0\) になります。

\(K\) が \(2, 3, 5, 7\) のみで構成されている場合は、桁を上から決めていきながら、現在の目標値 \(val\)（初期値は \(K\)）をその桁の数字 \(d\) で割っていくことで、残りの桁で必要な積を管理できます。

---

アルゴリズム

桁DPをメモ化再帰（DFS）を用いて実装します。

状態の定義

再帰関数 dfs(idx, is_less, is_started, val) を定義します。

• idx: 現在決めている桁のインデックス（上から idx 桁目）。
• is_less: 現在決めている数が、すでに \(N\) 未満であることが確定しているかどうか（未満フラグ）。
  • False の場合、この桁で選べる数字の上限は \(N\) の同じ桁の数字になります。
  • True の場合、この桁では \(0 \sim 9\) のどの数字でも選べます。
• is_started: すでに \(1\) 以上の数字を置き始めているかどうか（リーディングゼロ防止フラグ）。
  • 例えば \(N=123\) に対して \(25\) という数を考えるとき、上から \(1\) 桁目を「数がない（\(0\)）」として扱いたいです。この「実質的な桁数の調整のための \(0\)」を置いている間は is_started = False とし、積の計算から除外します。
• val: 残りの桁で達成すべき積の目標値。

遷移

各桁で数字 \(d\) を選ぶときの遷移は以下の通りです。

1. まだ数字の決定が始まっていない場合 (is_started = False)

   • \(0\) を選ぶ：数字をまだ置かないことを意味します。is_started は False のままで、目標値 val も変化させずに次の桁へ進みます。
   • \(1 \sim limit\) を選ぶ：ここから数字の決定が始まります。is_started を True にし、val を \(d\) で割った値（\(val\) が \(d\) で割り切れる場合のみ）を次の目標値として進みます。

2. すでに数字の決定が始まっている場合 (is_started = True)

   • \(0\) は選べません（積が \(0\) になってしまうため）。
   • \(1 \sim limit\) のうち、現在の val を割り切れる数字 \(d\) を選び、目標値を val // d に更新して次の桁へ進みます。

最後の桁まで到達したとき、is_started が True かつ val == 1 であれば、条件を満たす数を \(1\) つ作れたことになるので 1 を返し、そうでなければ 0 を返します。

---

計算量

• 時間計算量: \(O(D \times d(K))\)

  • \(D\) は \(N\) の桁数（\(D \le 18\)）です。
  • \(d(K)\) は \(K\) の約数の個数です。
  • \(K \le 10^{18}\) かつ素因数が \(2, 3, 5, 7\) のみに限られるとき、約数の個数は最大でも \(5 \times 10^4\) 程度に収まります。さらに、実際に探索で到達可能な状態数はこれより遥かに少ないため、実行時間制限（通常 2.0 秒）に対して非常に高速（数十ミリ秒程度）に動作します。

• 空間計算量: \(O(D \times d(K))\)

  • メモ化テーブル（連想配列 memo）に保存される状態数に比例します。時間計算量と同様に十分に小さく、メモリ制限を余裕でクリアできます。

---

実装のポイント

1. 再帰の上限変更: Pythonでは再帰の深さ制限の初期値が小さいため、sys.setrecursionlimit(2000) で上限を増やしておきます。

2. メモ化の工夫: is_less が False の状態（\(N\) と同じ数字をなぞっている状態）は、探索全体で各桁につき高々1回しか通りません。そのため、is_less = True（\(N\) 未満が確定している状態）のときのみメモ化テーブルに記録・参照することで、無駄なメモリ使用と連想配列の検索コストを削減しています。

3. 高速な素因数判定: \(K > 0\) のとき、あらかじめ \(2, 3, 5, 7\) で割れるだけ割り、残った値が \(1\) より大きければ、構成不可能として即座に 0 を返す枝刈りを行っています。

   ソースコード

import sys

# 再帰上限の変更
sys.setrecursionlimit(2000)

def solve_no_zero(N):
    if N < 1:
        return 0
    S = str(N)
    D = len(S)
    memo = {}
    
    def dfs(idx, is_less, is_started):
        if idx == D:
            return 1 if is_started else 0
        
        if is_less and (idx, is_started) in memo:
            return memo[(idx, is_started)]
        
        limit = 9 if is_less else int(S[idx])
        res = 0
        
        if not is_started:
            # 0 を選ぶ
            res += dfs(idx + 1, True, False)
            # 1 ~ limit を選ぶ
            for d in range(1, limit + 1):
                res += dfs(idx + 1, is_less or (d < limit), True)
        else:
            # 0 は選べない
            for d in range(1, limit + 1):
                res += dfs(idx + 1, is_less or (d < limit), True)
                
        if is_less:
            memo[(idx, is_started)] = res
        return res
        
    return dfs(0, False, False)

def solve(N, K):
    if N < 1:
        return 0
    if K == 0:
        return N - solve_no_zero(N)
    
    # K > 0 の場合、2, 3, 5, 7 以外の素因数を持っていれば構成不可
    temp = K
    for p in (2, 3, 5, 7):
        while temp % p == 0:
            temp //= p
    if temp > 1:
        return 0
    
    S = str(N)
    D = len(S)
    memo = {}
    
    def dfs(idx, is_less, is_started, val):
        if idx == D:
            return 1 if (is_started and val == 1) else 0
        
        if is_less and (idx, is_started, val) in memo:
            return memo[(idx, is_started, val)]
        
        limit = 9 if is_less else int(S[idx])
        res = 0
        
        if not is_started:
            # 0 を選ぶ
            res += dfs(idx + 1, True, False, val)
            # 1 ~ limit を選ぶ
            for d in range(1, limit + 1):
                if val % d == 0:
                    res += dfs(idx + 1, is_less or (d < limit), True, val // d)
        else:
            # 0 は選べない（積が 0 になってしまうため）
            for d in range(1, limit + 1):
                if val % d == 0:
                    res += dfs(idx + 1, is_less or (d < limit), True, val // d)
                    
        if is_less:
            memo[(idx, is_started, val)] = res
        return res

    return dfs(0, False, False, K)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    L = int(data[0])
    R = int(data[1])
    K = int(data[2])
    
    ans = solve(R, K) - solve(L - 1, K)
    print(ans)

if __name__ == '__main__':
    main()

---

この解説は gemini-3.5-flash-thinking によって生成されました。