Let’s take Sample 2 as an example. In order to travel between every pair of towns, \((\pm1,0),(\pm2,0),(\pm3,0)\) are necessary, but the latter two moves are actually not needed because it can be achieved by repeating \((\pm1, 0)\) multiple times.

As a generalization, we may claim as follows:

• Let \((X,Y)\) be the delta of coordinates when traveling from Town \(i\) to Town \(j\). Also, suppose that \(X\) and \(Y\) are both divisible by \(d\). Then, rather than remembering spell \((X,Y)\), it is better to remember \((\frac{X}{d}, \frac{Y}{d})\).

Therefore, once we know \((X, Y)\), the delta of coordinates, then we can divide the same number until \(X\) and \(Y\) do not have any common divisors greater than or equal to \(2\) in order to determine the spell to remember. It is actually known that it can actually be found by dividing \(X\) and \(Y\) by their greatest common divisor (GCD).

By the observations above, we can show that it is optimal to do the following operation for every distinct pair of towns \((i,j)\).

• Consider traveling from \((x_i, y_i)\) to \((x_j, y_j\)).
  First, let \(X = x_j - x_i, Y = y_j - y_i\). Then, let \(g = \gcd(X, Y)\), and transform as \(X \gets \frac{X}{g}, Y \gets \frac{Y}{g}\). Finally, remember the spell \((X, Y)\).

The time complexity of \(\gcd(X,Y)\) is \(\mathrm{O}(\log \max(X,Y))\). Hence the problem has been solved in a total of \(\mathrm{O}(N^2 \log \max(X,Y))\) time.