Discuss SRM 490 there.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
Name |
---|
ans = abs( N - gcd( N, M ) ) / 2.00 ???
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
Or Is there any other approach to this question?
check this link & its 2nd page!