ivan.popelyshev's blog

SRM 490
By ivan.popelyshev, 13 years ago, translation, In English
Discuss SRM 490 there.
  • Vote: I like it
  • +7
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
what is the proof of the div2 500 soln:

ans = abs( N - gcd( N, M ) ) / 2.00 ???
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Assume D = GCD(N, M)
    Waiting time of starship is a divisor of D, because it is always linear combination of N and M.
    Assume waiting time of i-th starship is ai.
    ai + 1 = ( - i * M)modN, a0 = aN = 0,  , so the sequence is linear and has a period. The answer is an average value of one period of the sequence.
    D = x * N + y * M for some x, y (extended euclidian algorithm ), so ay = N - D, hence every k * D , 0 <  = k * D < N is found in the sequence.
    The answer is average of  k * D where 0 <  = k * D < N which is (N - D) / 2.0
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it
      Can't i solve this question by iterating all the sequence till suppose eg. 100000000 (taking it as infinity)?

      Or Is there any other approach to this question?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        http://forums.topcoder.com/?module=Thread&threadID=695574&start=0

        check this link & its 2nd page!
        → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Thanks a lot for the proof :D
→ Reply