There are Two Chickens in the Line

2 secs 1024 MB
RedSpica's icon RedSpica

簡単のために整数XXが書かれているマスを単にマスXXと呼びます.

dd11つ決めたとします. tt秒後にいるマスは いっきゅうはマス(N+t)(N+t),にっきゅうはマス(d×t)(d \times t)です.

いっきゅうとにっきゅうが出会うということは,これらの整数が一致するので, これを解くと N=(d1)×tN = (d-1) \times t を得ます.

ここで,いっきゅうとにっきゅうが必ず出会うとすると, 出会う時間は一意に定まります.

また,上の式が示している重要な事実として, 「ddの候補はNNの約数に11を足したもののみである」 ということが導かれます.

よって,NNの約数をすべて列挙して,実際に条件を満たしているかを見ればよいです.

時間計算量はO(N)O( \sqrt{N} )です.