https://atcoder.jp/contests/abc210/submissions/24941318
最小全域木にクラスカル法というアルゴリズムがある。クラスカル法は「全ての頂点が連結になるまでコスト昇順に辺を選択してく」アルゴリズムだが、頂点と辺の数が多いため愚直にクラスカル法は使えない。そこで、クラスカル法を使わずに計算（シミュレーション）で処理する方針を取る。
最も自明なケースとして と互いに素な
があった場合
は全て異なる値になるので、その
だけで全て連結になる。そうでないとき、例えば頂点数18で
を選んだとすると連結成分は2個になるが、これは
と等しい。これは無限長の双六で考えるとサイコロの目が6と8と10だった場合、どれも2の倍数なので無限回数投げると止まるマスは2の倍数なら全て可能性が出てくる、という説明が分かりやすいと思う。一般化すると
を選ぶと連結成分の個数は
ということになる。
上記考察をまとめると以下のような処理で答えが求まる。
クラスカル法の考え方で最小全域木を構築するためコスト昇順にソートし、順番に を使っていくことにする。このとき
で辺を追加した結果、連結成分の個数が
になったとするとコスト合計は
だけ増えることになる（
は
を使って辺を1つ追加したときのコストとする）。連結成分の個数は gcd なので gcd = 1 になるまで繰り返せばコスト合計が求まる。なお
なら連結成分が1個にならないということなので -1 を出力する。
感想: この gcd の性質は初めて知った
