Editorial

数列の$i$項目まで決めたとき、$i+1$項目を決める操作は以下のような式で表すことができます。

• $i$項目までを10進整数と見たときの値を$A_i$, 次の項を$a_{i+1}$とすると$A_{i+1} = 10A + a_{i+1}$

また、合同式の性質より以下が成り立ちます。

• ある整数$a, b$について$a \equiv b \pmod{K}$ならば任意の整数$c$において$ac \equiv bc \pmod{K}, \hspace{0.5em} a+c\equiv b+c \pmod{K}$

このような事実より、$i$項目まで決めるときに$A_{i-1}$までを$K$で割ったあまりだけを見ていけば良いということがわかります。
よって、以下のようなDPテーブルを得ます。

• $\mathrm{dp}[i][j] = i$項目まで決めたときに$K$で割ったあまりが$j$となることはあるか?

また、以下のような遷移式を考えます。

• $\mathrm{dp}[i][j] = 1$ならば$\mathrm{dp}[i+1][(10j+a_1)\%K], \ \mathrm{dp}[i+1][(10j+a_2)\%K], \ ... , \ \mathrm{dp}[i+1][(10j+a_M)\%K] = 1$
• $\mathrm{dp}[i][j] = 0$ならば何もしない

答えは$\mathrm{dp}[i][0] = 1$となる最大の$i$です。

したがって$O(NK)$でこの問題が解けました。$N,K$は最大でも$10^3$と小さいので$NK$回の計算でも十分高速です。

ここではDPをしていますが一項前までで作れる数の$\mod K$での値をsetなどで持っておく、BFS的に実装するというようなことも可能です。
以下にC++での実装例を示していますが、$\mathrm{dp}[i-1][j] = i(i \ge 1)$項目まで決めたときの...としていることに注意してください。

類題 : ABC240_C - Jumping Takahashi

実装例(C++)