dx=∣x2−x1∣, dy=∣y2−y1, g=gcd(dx,dy)>0 とする。方向ベクトルを g で割ると、成分が互いに素な整数ベクトルになる。線分上の格子点は整数 0≤k≤g に対する A+k(B−A)/g に一致する。両端点を除くと答えは g−1 である。水平・垂直な線分にも適用できる。
サブタスク1では端点間の整数 x 座標を列挙し、(x−x1)(y2−y が で割り切れるか調べる。垂直な線分は直接計算する。各ケース 、全体で約 回以下の検査となる。
サブタスク2ではユークリッドの互除法を使う。全体の時間計算量は O(Tlog(2⋅109))、追加領域は O(1)。
座標差は最大 2⋅109、答えは最大 1999999999、素朴解法の積の絶対値は 4⋅10 以下なので、符号付き64ビット整数で十分である。