SRM390 Div2 500

問題

正の整数numberが与えられる。そのnumberのコピーをいくつかくっつけてできる数字の中で、kで割り切れるものを探す。そのような数字で一番小さい数字のコピー回数を返す。無理なら-1を返す。

考え方

kで割り切れるということで、余りに注目する。
numberをkでわって、その余りが0ならば割り切れる。
0でないならば、numberの後ろにnumberをくっつける。するとくっつけた数字の余りは、くっつける前の余り*10^n+numberになることがわかる。nはnumberの桁+1。
これを繰り返し、0になるまでの回数を数える。
また、同じ余りが出た場合はループしているので、余りをメモしておいて、同じ余りがでたら-1を返す。

反省

「kで割り切れる」から素因数分解することしか頭になかった。けど、その方法だと、numberを2つ以上繋いだ状態が表現できないので、無理。
割り切れるとは余りが0になるということ。