D - Small Multiple

D - Small Multiple

問題概略

正の数Nにある倍数をかけて桁の和を最小にしたい

制約

• $2\le K\le {10}^5$
• $K$ は整数である

解法

modKで考えるとグラフの遷移で書ける

コストの合計が桁の和になればよく、すべての数が作れればよい。*10,+1があればすべての数が作れる。

+1なら合計は1増え、*10なら変わらない。