spirited_away_'s blog

By spirited_away_, history, 5 months ago, , In problem small multiple , you are asked to the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

what i did was i ran a loop from 1 to 70000000 and compute answer for each i. It gave WA in some test cases. 16/66 MY solL:

The editorial mentions Construct a graph with K vertices, start from 1 and answer will be minimum distance from 1 to 0 , +1.

Though i understood the editorial, But i couldn't get the proof behind it. why it will give right answer. Why we are creating only k vertices and considering each number as x % k.

Can anyone who solved it, explain the logic behind it. Or any other approach for solving this problem. Comments (7)
 » Can someone explain me these lines in the editorial , : Note: Isn't the trouble with '9' important? Suppose that the algorithm above finds an invalid solution that contains a digit "10" at position i. However, due to the periodicity of powers of tens, (whenKis comprime to 10) we can find another j such that 10^i and 10^j are the same in modulo K, so we can move one digit fromi to j. Even when K is not coprime to 10, we canmake it periodic by attaching sufficient number of zeroes at the end.
•  » » since upto 9 digit sum will increase, but when we will encounter 10, sum will decrease, then why we r still adding 1?
•  » » » i implemeted the editorial , https://atcoder.jp/contests/abc077/submissions/5545298but still couldn't understand the last part , someone pls tell .