最下位桁で場合分けをし，メモ化再帰で書く方法を紹介します．

問題文では「\(N\) 以下の正の整数」になっていますが，ここでは \(0\) も含めて数えて，最後に答えから \(1\) を引くことにします．また，「\(0\) の各桁の数字の積は \(1\) である」と定めます．これは，\(0\) を \(1\) 桁の数ではなく \(0\) 桁の数として扱い，\(0\) 個の数の積は \(1\) であると定めると導かれます．

問題の答え，すなわち，「非負整数 \(X\) のうち，条件

1. \(X \leq N\)
2. \(X\) の各桁の数字の積が \(K\) 以下

をともに満たすものの個数」を \(a(N, K)\) とおきます．\(a(N, K)\) を以下の \(3\) 通りに場合分けして計算します．

• \(X = 0\) の場合（\(X\) の一の位が無い場合）:
  「\(0\) の各桁の数字の積は \(1\) である」としたので，条件を満たす \(X\) は，\(K \geq 1\) の場合は \(1\) 個，\(K = 0\) の場合は \(0\) 個あります．
• \(X\) の一の位が \(0\) の場合 :
  \(X = 10x\) と書けます \((x \geq 1)\)．このとき，条件 1 は \(x \leq \big\lfloor \frac{N}{10} \big\rfloor\) と変形でき，条件 2 は無条件に満たされます．よって，条件を満たす \(X\) は \(\big\lfloor \frac{N}{10} \big\rfloor\) 個あります．（\(\lfloor x \rfloor\) は \(x\) 以下の最大の整数を表します．）
• \(X\) の一の位が \(y\) \((1 \leq y \leq 9)\) の場合:
  \(X = 10x + y\) と書けます \((x \geq 0)\)．このとき，条件 1 は \(x \leq \big\lfloor \frac{N - y}{10} \big\rfloor\) と変形でき，条件 2 は「\(x\) の各桁の数字の積が \(\big\lfloor \frac{K}{y} \big\rfloor\) 以下である」と言い換えられます．よって，条件を満たす \(X\) は \(a\big( \big\lfloor \frac{N-y}{10} \big\rfloor, \big\lfloor \frac{K}{y} \big\rfloor \big)\) 個あります．

以上より，漸化式

\[a(N, K) = \mathbf{1}[ K \geq 1] + \Big\lfloor \frac{N}{10} \Big\rfloor + \sum_{y=1}^9 a\Big( \Big\lfloor \frac{N-y}{10} \Big\rfloor, \Big\lfloor \frac{K}{y} \Big\rfloor \Big)\]

が得られます（\(\mathbf{1}[ K \geq 1]\) は \(K \geq 1\) ならば \(1\)，そうでないならば \(0\) をとります）．あとはこれをメモ化再帰で実装すればよいです．計算量の解析は公式解説と同様です．

実装例 (C++, 380 Byte)