\(1\) 以上 \(10^9\) 以下の整数 \(n\) に対して、\(d(n)\) がとりうる値の範囲は \(1\) 以上 \(81\) 以下です。この値を決め打ったときの \(n\) の最大値を求める方法を考えます。
\(d(n) = K\) とおくと、\(n\) の満たすべき条件は以下の三つです。

• \(1 \leq n \leq 10^9\)
• \(d(n) = K\)
• \(A \times n + B \times K \leq X\)

三つ目の条件は \(n \leq \left\lfloor\frac{X - B \times K }{A} \right\rfloor\) と変形できます。\(Y = \min (10^9, \left\lfloor\frac{X - B \times K }{A} \right\rfloor )\) とおくと、次のように条件をまとめることができます。

• \(1 \leq n \leq Y\)
• \(d(n) = K\)

これらを満たす \(n\) の最大値を次のように場合分けして求めます。

[1] \(n\) が一桁の整数のとき

\(1 \leq K \leq 9\) かつ \(K \leq Y\) が成り立つとき、またそのときに限り条件を満たす \(n\) が存在し、その値は \(K\) です。

[2] \(n\) が二桁以上の整数のとき

\(n = 10a + b\) となる \(1\) 以上の整数 \(a\) および \(0\) 以上 \(9\) 以下の整数 \(b\) が存在します。二つの条件は次のように言い換えられます。

• \(1 \leq a \leq \left\lfloor\frac{Y - b}{10} \right\rfloor\)
• \(d(n) = K - b\)

\(b\) を固定すれば上の条件を満たす \(a\) の最大値を求める問題に帰着でき、元の問題において \(Y \leftarrow \left\lfloor\frac{Y - b}{10} \right\rfloor, K \leftarrow K - b\) とした場合と一致します。

これらを踏まえて次のような再帰関数を定義します。

• \(\mathrm{solve}(y, k)\) : \(1 \leq n \leq y\) かつ \(d(n) = k\) を満たす \(n\) の最大値を求める。
• \(y, k\) のいずれかが \(0\) 以下のとき、\(-\infty\) を返す。そうでないとき、以下の値の最大値を返す。
  • \(1 \leq k \leq 9\) かつ \(k \leq y\) のとき \(k\)、そうでなければ \(-\infty\)
  • \(b = 0, 1, \dots, 9\) に対する \(10 \times \mathrm{solve}(\left\lfloor\frac{y - b}{10} \right\rfloor, k - b) + b\) の最大値。

\(K = 1, \dots, 81\) に対する \(\mathrm{solve}(Y, K)\) の最大値が答えとなります。実は関数 \(\mathrm{solve}\) をメモ化することで実行時間制限に間に合います。
計算量を解析しましょう。まず、\(k\) の値は \(81\) 通り程度であり、再帰の深さは \(\log_{10} Y\) 程度です。深さ \(d\) における \(y\) の値は次のように評価することができます。

• \(y \leq \frac{\frac{\frac{Y - 0}{10} - 0}{10} - 0}{10}_\ddots \leq \frac{Y}{10^d} \)

• \(y \geq \frac{\frac{\frac{Y - 9}{10} - 9}{10} - 9}{10}_\ddots \gt \frac{Y}{10^d} - 1\)

よって各深さにおける \(y\) の値は高々 \(2\) 通りです。以上から、\(\mathrm{solve}(y, k)\) の呼び出しにおける \(y, k\) の値の組は \(81 \times 2 \log_{10}{Y}\) 通り程度なので、メモ化して実装することで実行時間制限に余裕を持って間に合います。