サンプル 2 を例に考えてみましょう。すべての街同士を行き来したい場合は \((\pm1,0),(\pm2,0),(\pm3,0)\) が必要ですが、後ろの \(2\) つは \((\pm1, 0)\) を複数回繰り返せば移動できるので不要でることがわかります。

これをより一般化すると、次のようなことが言えると思います。

• 街 \(i\) から街 \(j\) へ行くときの座標の変化が \((X,Y)\) だとする。また、 \(X, Y\) はどちらも \(d\) で割り切れる。このとき、魔法 \((X,Y)\) を覚えるよりも魔法 \((\frac{X}{d}, \frac{Y}{d})\) を覚える方がよい。

ここから、座標の変化 \((X,Y)\) が分かった時に、 \(X,Y\) に共通する \(2\) 以上の約数が存在しなくなるまで \(X,Y\) から同じ数を割り続ければ覚えるべき魔法が特定できます。このような操作を行いたい場合、実は \(X\) と \(Y\) の最大公約数 (GCD) と呼ばれる数を割ればよいということが知られています。

以上の考察により、すべての異なる街の組 \((i,j)\) に対して次の操作を行うことが最適であることが示せます。

• \((x_i, y_i)\) から \((x_j, y_j)\) に行くことを考える。
  まず、\(X = x_j - x_i, Y = y_j - y_i\) とする。
  次に \(g = \gcd(X, Y)\) として \(X \gets \frac{X}{g}, Y \gets \frac{Y}{g}\) に変換する。そして、魔法 \((X, Y)\) を覚える。

\(\gcd(X,Y)\) の計算量は \(\mathrm{O}(\log \max(X,Y))\) です。以上よりこの問題を \(\mathrm{O}(N^2 \log \max(X,Y))\) で解くことができました。