Codeforces Beta Round #51 A

問題

ノミがn個の円状になっている草むらを時計回りで飛んでいる。このノミは時刻kのときには、現在位置からk-1個先の草むらへ飛ぶ。このとき、ノミはn個すべての草むらにまわることができるか。

考え方

nが少ないので、適当にシミュレーションするだけ。

なのだけれども、実際は、nは2の冪乗(n=2^m,m=0,1,2,...)の時だけ全ての草むらに回ることができることがわかる。
なぜ？という証明が http://codeforces.ru/blog/entry/1110 にあったので以下に書き写す。
■証明
nが2の冪乗であることを仮定する。
k回目に飛んだときにノミのいる場所は、1+2+3+...+k=k(k+1)/2 mod nである。
k1回目とk2回目が同じ場所なら、
k1(k1+1)/2≡k2(k2+1)/2 mod n
なので、
(k1-k2)(k1+k2+1)/2≡0 mod n
なはずだけど、(k1-k2)と(k1+k2+1)は偶奇性から奇数にしかならないので、n=2^mであれば割り切れない。
したがって、n=2^mの時は(k1回目の場所)!=(k2回目の場所)なので、(n-1)回目まですべて違う場所にいるはずである。すなわち、n=2^mであれば、すべての場所へまわれる。

もし、nが2の冪乗でないならば、nには2以上の(奇数の)素数で割ることができるはずである。
ここで、素数pに対してmod nでなくmod pを考える。(nをp個ずつ(n/p)グループに分割するイメージ)
(素数の)p回目にいる場所は1+2+...+p=p(p+1)/2であるが、これはpで割り切れるので、mod pで余りが0の場所と同じ場所に戻るはず。(p-1)回目の場所も(p-1)p/2でpで割り切れる。(p-1)回目の(余りが0の)場所からジャンプするとp回目の(再び余りが0の)場所に戻るので、すなわち(p-1)回目が違う場所に飛ぶ最後の場所である。
しかし、(p-1)回目の時点でmod pで(p-1)回目がpで割り切れてしまうので、すべての余りの場所を通ることができないことがわかる。p回目は(mod pで)0回目と同じ場所に戻るので、どんなに繰り返してもすべての場所を回ることができない。

■要約
nに3以上の素数が含まれる場合、nをその素数p個ずつにグループ分けしたら、mod pですべてを周れずに循環してしまうので、3以上の素数を含めてはいけない。すなわち、nは1か素因数として2しか持つ数でなければならない。これは2の冪乗である。