Discuss SRM 490 there.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
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!