AtCoder Regular Contest 152 D - Halftree
メモ
木を生成できるような操作列を求めろ。
ここで操作とはu-vに辺を貼ったときに(u+K)%N, (v+K)%Nに辺が貼られるようなものである
Nが奇数の時だけ考える
k==1の時にパスを作りたくなる
また、g=gcd(N, K)でg==1なら、0-KとKずつ増やすことで同様にパスが作れる
g!=1の場合、0,1,...g-1からスタートしてKずつ増やした時に互いに独立する
そこでそれぞれの列について長方形のように並べたくなる
以下のように、スタートした値ごとに、Kずつ足して得られる順番に縦に並べる。
N==奇数であるため 奇数*奇数の長方形ができる
以下のように結ぶと木が得られる
