There are Two Chickens in the Line

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

$d$を$1$つ決めたとします． $t$秒後にいるマスは いっきゅうはマス$(N+t)$，にっきゅうはマス$(d \times t)$です．

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

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

また，上の式が示している重要な事実として， 「$d$の候補は$N$の約数に$1$を足したもののみである」 ということが導かれます．

よって，$N$の約数をすべて列挙して，実際に条件を満たしているかを見ればよいです．

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