Let , , and . Dividing the direction vector by gives a primitive integer vector. The lattice points on the segment are exactly for integers . Excluding both endpoints leaves points. The formula also covers horizontal and vertical segments.
Subtask 1: enumerate integer x-coordinates strictly between the endpoints and test divisibility of by . Handle vertical segments directly. This takes time per case, at most about checks overall.
Subtask 2: compute the gcd with the Euclidean algorithm. Total time is with auxiliary space.
Coordinate differences are at most , the answer is at most , and the naive product has magnitude at most . Signed 64-bit integers suffice.