\(L=1\) の場合についての問題を解くことができれば、\(R\) に \(L-1\) を代入した問題についても解くことで答えを求めることができます。したがって、以降は \(L=1\) の場合を考えます。

\(K=0\) の場合と \(K>0\) の場合で場合分けします。

1. \(K=0\) のとき

\(1\) 以上 \(R\) 以下で十進表記に \(0\) がつく整数の個数が求まれば良いです。

\(g(N)\) を \(N\) 以下の正整数で十進表記に \(0\) が つかない ものの個数とします。求める値は \(N-g(N)\) です。

\(N < 10\) なら \(g(N)=N\) です。また、\(N \geq 10\) なら \(1\) の位を考えることで \(\displaystyle g(N)=9+\sum_{c=1}^9 g\left(\left\lfloor \frac{N-c}{10}\right\rfloor \right)\) という漸化式が従います。

あとはこの式をもとにメモ化再帰などを用いつつ \(g(R)\) の値を計算することができます。

2. \(K>0\) のとき

\(f(N,K)\) を \(N\) 以下の正整数で桁毎の積がちょうど \(K\) となる整数の個数とします。

\(N < 10\) のとき、\(f(N,K)=1_{N \geq K}\) です。

\(N\geq 10\) のとき、 \(\displaystyle f(N,K) = 1_{K < 10}+\sum_{\substack{1\le c < 10\\ k \equiv 0 \bmod c}}f\left(\left\lfloor \frac{N-c}{10}\right\rfloor,\frac Kc \right)\) という漸化式が成り立ちます。これもメモ化再帰を用いつつ高速に計算することができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

from functools import cache


@cache
def f(x, k):
    if x < 10:
        return 1 if k <= x else 0
    ans = 1 if k < 10 else 0
    for c in range(1, 10):
        if k % c != 0:
            continue
        ans += f((x - c) // 10, k // c)
    return ans


@cache
def g(x):
    if x < 10:
        return x
    ans = min(9, x)
    for c in range(1, 10):
        ans += g((x - c) // 10)
    return ans


l, r, k = map(int, input().split())
l -= 1
if k == 0:
    print(r - g(r) - l + g(l))
else:
    print(f(r, k) - f(l, k))