Блог пользователя spirited_away_

Автор spirited_away_, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.