SRM490 Div2 500

とぷこだ 過去問

問題

新しい宇宙港が稼動しはじめた。
宇宙船は(0分から始まって)M分毎にこの新しい宇宙港に到着する。
そして、この宇宙港はN分毎に停泊している宇宙船をテレポートさせることができる。
もし、同時刻についた場合でも着いたと同時にテレポートできる。
宇宙船の待ち時間の平均を求める。


M*i分に到着した宇宙船の待ち時間をW(i)で表すと、平均時間は( W(0)+W(1)+...+W(P-1) )/Pと書ける。Pは正の無限大であり、この値は有限であることが補償される。
1<=N,M<=10^9

考え方

普通に計算すると10^9までなので、無理。したがって数学的に解くしかない。
サンプルを紙に書いていると、有限の部分の繰り返しであることがわかる(Nの倍数とMの倍数が一致するところ)。
さらに、NとMが互いに素な時、その値は0〜N-1であることがわかる。
NとMが互いに素でない場合は、各値がgcd(N, M)倍されていると考えると0〜N/gcd-1であることがわかり、答えは平均のgcd倍すればよい。

int g = gcd(N, M);
int n = N/g; //0〜n-1までの待ち時間がでてくるはず
//(0〜n-1までの和)/n*g倍 = n*(n-1)/n/2*g = (n-1)*g/2
return (n-1)/2.0*g;

手を動かしていれば0〜N-1までの数字がでてくることは見つかるとしても、常に出てくるか証明できないときつい。
というか、互いに素な場合とそうでない場合がごっちゃになってしまう。


tomerunさんが背理法で証明を載せていたので、そのままながら勉強。
URL: http://topcoder.g.hatena.ne.jp/tomerun/20101210/1292002406
「NとMが互いに素な場合、lcm(N, M)まで差が0〜N-1の数字がでる」
でてこないと仮定。すると、aM以上の最小のNの倍数cNとbM以上の最小のNの倍数dNから(cN-aM) = (dN-bM)と書ける整数a,b,c,dが存在する。これを書き直すと、「aM ≡ bM (mod N)となるMの倍数がある(1 <= a < b < N)」と書ける。これが正しいかというと、移項して「(b-a)M ≡ 0 (mod N)」となり(b-a)MがNで割り切れることになるので、NとMが互いに素なら(b-a)がNの倍数であるはず。しかし、「b < N」→「 b-a < N-a < N 」→「b-a < N」でb-aがNより小さいのでNの倍数でない。これは矛盾するので、差が同じものがでてこない。mod Nなので、0からN-1までの数字が全てでてくる。