dx=∣x2−x1∣, dy=∣y2−y1, g=gcd(dx,dy)라 하자. 두 점이 다르므로 g>0이다. 방향 벡터를 g로 나누면 두 성분이 서로소인 정수 벡터가 된다. 따라서 선분 위 격자점은 A+k(B−A)/g (0≤k≤g)이며, 양 끝점을 제외하면 정답은 g−1이다. 한 성분이 0인 수평·수직 선분에도 같은 식이 성립한다.
서브태스크 1은 정수 x 좌표를 순회하며 (x−x1)(y2−이 로 나누어떨어지는지 검사한다. 수직 선분은 별도로 계산한다. 케이스당 이므로 전체 최대 약 번의 검사가 필요하다.
서브태스크 2는 유클리드 호제법으로 최대공약수를 구한다. 전체 시간 복잡도는 O(Tlog(2⋅109)), 추가 공간은 O(1)이다.
좌표 차이의 절댓값은 최대 2⋅109, 정답은 최대 1999999999이다. 나이브 풀이의 곱의 절댓값도 4⋅10 이하이므로 모든 계산은 부호 있는 64비트 정수로 안전하다.