概要

区間 \([L,R]\) に含まれる整数のうち、「十進表記の各桁の積」\(f(n)\) がちょうど \(K\) になる個数を数えます。\(R\le 10^{18}\) と非常に大きいので、全探索ではなく桁DPで数え上げます。

考察

重要な観察1：\(K>0\) のとき、使える素因数は \(2,3,5,7\) だけ

各桁は \(1\)〜\(9\)（\(0\) は積を \(0\) にしてしまうので \(K>0\) のとき禁止）で、
\(1..9\) の素因数は \(2,3,5,7\) のみです。例えば - \(8=2^3\) - \(9=3^2\) - \(6=2\cdot 3\) - \(5=5\)

よって \(K\) を素因数分解して、\(2,3,5,7\) 以外の素因数が残るなら（例：\(K\) が \(11\) を含むなど）絶対に作れないので答えは \(0\) です。
コードでは factorize_k で \(K\) から \(2,3,5,7\) を割り尽くし、最後に \(1\) にならなければ不可能と判定しています。

重要な観察2：\(K=0\) は別処理が簡単

\(f(n)=0\) になるのは「どこかに桁 \(0\) を含む」場合に限ります。
したがって - 区間の総数 \((R-L+1)\) から - 「0を含まない数」の個数

を引けばよいです。
この「0を含まない数」も桁DPで \([1,n]\) まで数えられます（count_nozero_leq）。

なぜ素朴解は無理か

\(R\) が最大 \(10^{18}\) なので、区間の長さが最大で \(10^{18}\) 個になります。各 \(n\) に対して桁の積を計算して判定するのは当然間に合いません。
そこで「上限 \(n\) 以下で条件を満たす個数」を桁DPで数え、差分で区間を求めます。

アルゴリズム

1. 前処理：各数字 \(d(0..9)\) の \((2,3,5,7)\) 指数を作る

各桁 \(d\) を素因数分解し、 [ d = 2^{e2}\cdot 3^{e3}\cdot 5^{e5}\cdot 7^{e7} ] となる \((e2,e3,e5,e7)\) を DIG_FACT[d] に持っておきます。例： - DIG_FACT[8]=(3,0,0,0) - DIG_FACT[6]=(1,1,0,0) - DIG_FACT[1]=(0,0,0,0)

2. \(K=0\) の場合

count_nozero_leq(n)：\(1\le x\le n\) のうち「一度数字が始まった後に 0 を使わない」数を桁DPで数えます。 - 状態：pos（何桁目まで見たか）, started（まだ先頭の0を読んでいるか）, tight（上限と一致しているか） - 遷移：まだ始まっていない started=0 のときは 0 を選んでもよい（桁を進めるだけ）。始まってからは 0 を禁止。

区間 \([L,R]\) の「0を含まない数」は
count_nozero_leq(R) - count_nozero_leq(L-1)
なので、求める答えは [ (R-L+1) - \text{nozero} ] です。

3. \(K>0\) の場合：指数の残りを管理する桁DP

まず \(K\) を [ K=2^{t2}\cdot 3^{t3}\cdot 5^{t5}\cdot 7^{t7} ] に分解し、それ以外の因子があれば不可能（答え \(0\)）。

次に count_prod_leq(n, (t2,t3,t5,t7)) で、\(1\le x\le n\) かつ \(f(x)=K\) の個数を数えます。

DPの状態

dfs(pos, e2, e3, e5, e7, started, tight) を - 上から pos 桁目まで決めた - まだ必要な指数（残り）が \((e2,e3,e5,e7)\) - started：まだ先頭の0部分か - tight：ここまで上限 \(n\) と一致しているか

と定義します。

遷移

• まだ started=0 で d=0 を選ぶ：数はまだ始まらないので指数は減らさない（先頭の0扱い）。
• それ以外で d=0 は禁止（\(K>0\) では積が 0 になってしまうため）。
• d=1..9 を置くとき、DIG_FACT[d]=(a2,a3,a5,a7) だけ指数を消費する。
  • もし a2<=e2 など全て満たすなら次状態へ（残り指数を引く）。
  • 満たさなければその桁は選べない（積が \(K\) を超える/別の因子が混ざることに相当）。

終端条件

桁をすべて見終わったとき（pos==len）、 - ちゃんと数が始まっていて（started=1） - 残り指数がすべて \(0\)

なら 1 通り、それ以外は 0 通り。

最後に区間はいつもの差分で [ \text{count}(L..R)=\text{count}(\le R)-\text{count}(\le L-1) ] です。

計算量

\(D=\text{桁数}\le 19\)、\(K=2^{t2}3^{t3}5^{t5}7^{t7}\) とすると

• 時間計算量:
  
  • \(K=0\) のとき：\(O(D\cdot 10 \cdot 2 \cdot 2)\) 程度（通常の桁DP）
    
  • \(K>0\) のとき：おおむね
    [ O\bigl(D\cdot (t2+1)(t3+1)(t5+1)(t7+1)\cdot 10\bigr) ] （tight/started を含めても定数倍）
• 空間計算量:
  
  • メモ化するDP状態数に比例し、 [ O\bigl(D\cdot (t2+1)(t3+1)(t5+1)(t7+1)\bigr) ] です。

※ \(K\le 10^{18}\) なので \(t2,t3,t5,t7\) はそれぞれ高々数十程度になり、現実的な大きさに収まります。

実装のポイント

• \(K=0\) を別処理にすると簡単で高速です（「0を含まない数」を引く）。

• \(K>0\) では 0の桁は必ず禁止（先頭の0を除く）。これを忘れると誤答になります。

• started を持ち、数がまだ始まっていない先頭の0列をきちんと扱う（最終的に started=0 のまま＝数が存在しないケースを数えない）。

• lru_cache でメモ化し、同じ状態を繰り返し計算しないようにする。

• \(K\) に \(2,3,5,7\) 以外の素因数が残ったら 即 0 を出す（桁の積では作れないため）。

  ソースコード

import sys
from functools import lru_cache

DIG_FACT = [(0, 0, 0, 0)] * 10
tmp = []
for d in range(10):
    x = d
    e2 = e3 = e5 = e7 = 0
    while x > 0 and x % 2 == 0:
        x //= 2
        e2 += 1
    while x > 0 and x % 3 == 0:
        x //= 3
        e3 += 1
    while x > 0 and x % 5 == 0:
        x //= 5
        e5 += 1
    while x > 0 and x % 7 == 0:
        x //= 7
        e7 += 1
    tmp.append((e2, e3, e5, e7))
DIG_FACT = tmp


def factorize_k(k: int):
    e2 = e3 = e5 = e7 = 0
    while k % 2 == 0:
        k //= 2
        e2 += 1
    while k % 3 == 0:
        k //= 3
        e3 += 1
    while k % 5 == 0:
        k //= 5
        e5 += 1
    while k % 7 == 0:
        k //= 7
        e7 += 1
    return (e2, e3, e5, e7), k


def count_nozero_leq(n: int) -> int:
    if n <= 0:
        return 0
    digits = list(map(int, str(n)))
    m = len(digits)

    @lru_cache(None)
    def dfs(pos: int, started: int, tight: int) -> int:
        if pos == m:
            return 1 if started else 0
        lim = digits[pos] if tight else 9
        res = 0
        for d in range(lim + 1):
            nt = 1 if (tight and d == lim) else 0
            if not started and d == 0:
                res += dfs(pos + 1, 0, nt)
            else:
                if d == 0:
                    continue
                res += dfs(pos + 1, 1, nt)
        return res

    return dfs(0, 0, 1)


def count_prod_leq(n: int, target_exps) -> int:
    if n <= 0:
        return 0
    digits = list(map(int, str(n)))
    m = len(digits)
    t2, t3, t5, t7 = target_exps

    @lru_cache(None)
    def dfs(pos: int, e2: int, e3: int, e5: int, e7: int, started: int, tight: int) -> int:
        if pos == m:
            return 1 if started and e2 == 0 and e3 == 0 and e5 == 0 and e7 == 0 else 0
        lim = digits[pos] if tight else 9
        res = 0
        for d in range(lim + 1):
            nt = 1 if (tight and d == lim) else 0
            if not started and d == 0:
                res += dfs(pos + 1, e2, e3, e5, e7, 0, nt)
            else:
                if d == 0:
                    continue
                a2, a3, a5, a7 = DIG_FACT[d]
                if a2 <= e2 and a3 <= e3 and a5 <= e5 and a7 <= e7:
                    res += dfs(pos + 1, e2 - a2, e3 - a3, e5 - a5, e7 - a7, 1, nt)
        return res

    return dfs(0, t2, t3, t5, t7, 0, 1)


def main():
    L, R, K = map(int, sys.stdin.readline().split())

    if K == 0:
        nozero = count_nozero_leq(R) - count_nozero_leq(L - 1)
        ans = (R - L + 1) - nozero
        print(ans)
        return

    target_exps, rem = factorize_k(K)
    if rem != 1:
        print(0)
        return

    ans = count_prod_leq(R, target_exps) - count_prod_leq(L - 1, target_exps)
    print(ans)


if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。