Atcoder abc077 , Problem : small multiple.

Revision en1, by spirited_away_, 2019-05-22 00:55:00

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. 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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English spirited_away_ 2019-05-22 00:58:12 48 Tiny change: 'behind it.\n\n' -> 'behind it. Or any other approach for solving this problem.\n\n'
en3 English spirited_away_ 2019-05-22 00:56:30 6 Tiny change: 'st cases. [MY solL:' -> 'st cases. 16/66 [MY solL:'
en2 English spirited_away_ 2019-05-22 00:55:34 4
en1 English spirited_away_ 2019-05-22 00:55:00 831 Initial revision (published)