ABC109-C
考えたこと
・初期地点も都市として扱い、都市のリストに追加。それらを位置でソートする。
・両端の都市の距離を用いて二分探索で隣り合う都市間の距離を割った余りが0になるように設定するとよいのでは?二分探索(O(logN))と各都市間距離を見ていく(O(N))のでちょうどO(NlogN)となり、計算量的には行けそう
・と思ったが、二分探索の終了がうまくできなかった。
・ならば素朴に各都市間の距離についてユークリッドの互除法で解くことを考える。ググるとユークリッドの互除法は計算量がO(logN)なので大丈夫そう
・いけた
*------------------*
学んだこと
ユークリッドの互除法はO(logN)