この問題は「集合\(\{1,10,100,\cdots\}\)からそれぞれ\(0\sim9\)個ずつ選んで総和を\(K\)の倍数とするときの選ぶ個数の最小値はいくつか？」と言い換えることができます。

ここで\(10^i \equiv 10^j\mod K\)であるような二数を合わせて\(10\)個以上選ぶ意味はないです。(\(10^i \)や\(10^j\)を\(10\)個選ぶ代わりに\(10^{i+1}\)を\(1\)つ選んだ方が桁和が小さくなるため。)

逆に言えば\(0\sim9\)個という制限をなくしても最小値は変わらないということです。さらに\(10^{K}\)以降は\(K\)の剰余が必ず被るので考慮する必要はありません。したがって以下のような問題に言い換えられます。

「集合\(\{1,10,100,\cdots,10^{K-1}\}\)からそれぞれ好きな個数ずつ選んで総和を\(K\)の倍数とするときの選ぶ個数の最小値はいくつか？」

これは以下のように解くことができます。

• \(\{1,10,100,\cdots,10^{K-1}\}\)を\(K\)で割ったあまりの集合を\(A\)とおく.
• \(f=a_0+a_1x+\cdots+a_{K-1}x^{K-1}(i\in Aのときa_i=1,それ以外では0)\)とおく.
• \(f^{n}\)の\(x^{ak}(aは非負整数)\)の係数が\(0\)でないような\(a\)が存在する最小の\(n\)が答え.

これは\(f\)をかける部分を畳み込みで求めることで高速に求めることが出来ます。また、\(f\)をかけるたびに\(x^{K}\)で割った剰余を求めて次数下げを行えば畳み込む長さを短縮でき、定数項部分だけをチェックすればよくなります。

答えは最大でも\(45\)以下になることが分かるので\(f\)をかけるのは最大でも\(44\)回であり制限時間に十分間に合います。