Discuss SRM 490 there.
# | User | Rating |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | -is-this-fft- | 148 |
5 | atcoder_official | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
9 | TheScrasse | 144 |
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!