\(B = 10\)（位取り記数法の基数）とします。桁和の最大値を \(L\) とすると、\(L\) は制約下で \(9 \times 10\) 以下（一般には \(L = O(B \log M)\) ）であることに注目します。

\(K\) が大きい場合

\(M\) 以下の正整数のうち、\(K\) で割ったあまりが \(L\) 以下のものだけを調べるとしてよいです。調べる整数の個数は \(O \left( M \cdot \dfrac{L}{K} \right) = O\left( \dfrac{BM\log M}{K} \right)\) です。桁和を求めるパートの計算量も考慮すると、時間計算量は \(O\left( \dfrac{BM\log^2 M}{K} \right)\) と評価できます。

\(K\) が小さい場合

桁 DP をします。

• \(\mathrm{dp}(i, j, k, b) := \) 上から \(i\) 桁目まで見て、\(K\) で割ったあまりが \(j\) で、桁和を \(K\) で割ったあまりが \(k\) で、\(b = 0\) なら \(M\) より小さいことが未確定、\(b = 1\) なら確定 という状態の個数

状態数は \(O(KL \log M) = O(KB \log^2 M)\) で、\(1\) 回の遷移に \(O(B)\) かかることから時間計算量は \(O(K B^2 \log^2 M)\) です。

ここまででも通ると思いますが、よく考えると \(j, k\) を両方持つ必要はなく、\(j - k \pmod K\) のみ管理すればよいです。これで状態数を \(O(K \log M)\) に削減でき、時間計算量は \(O(KB \log M)\) となります。

上記の解法を \(K\) の大きさによって使い分ければよいです。閾値を \(\Theta(\sqrt{M \log M})\) にすることで、時間計算量 \(O(B \sqrt{M} \log^{1.5} M)\) を達成できます。