D. Nezzar and Board 差の絶対値の全ペアのgcdはO(N^2)ではなくO(N)

• キッカケとなった問題
  • D.Nezzar and Board
  • https://codeforces.com/contest/1478/problem/D
• AC
  • https://codeforces.com/contest/1478/submission/105774949
• 解説
  • 2点間の距離を全部求めてgcd取ると飛び幅が求まる
  • しかしO(N²)かかる。なんとなく隣接だけ距離を求めてそれらのgcdで十分そうに思える
  • たぶん正しくて、理由は下図