2283. Integer Points on a Segment
A segment runs from A to B, both with integer coordinates. Print how many
points with INTEGER coordinates lie on the closed segment, endpoints included.
(0,0)-(4,0) -> 5 (0,0) (1,0) (2,0) (3,0) (4,0)
(0,0)-(4,4) -> 5 (0,0) (1,1) (2,2) (3,3) (4,4)
(0,0)-(5,3) -> 2 only the endpoints
## What most people try first
Walking the bounding box and testing each lattice point for collinearity. That
is correct, and at coordinates up to 10^6 the box can hold 4 * 10^12 points,
so it does not finish. The lesson here is that the count has a closed form and
does not need to be enumerated at all.
The second instinct is max(|dx|, |dy|) + 1, which is right for a horizontal,
vertical or exactly diagonal segment and wrong for everything else. For
(0,0)-(5,3) it claims six and the answer is two.
## The structure of the lattice points on a segment
Let dx = Bx - Ax and dy = By - Ay, and let g = gcd(|dx|, |dy|). Then the
step (dx/g, dy/g) is the SHORTEST step with integer components in the
direction of the segment, because dividing by the greatest common divisor is
exactly what makes the pair have no common factor left to remove.
Starting at A and taking that step g times lands on B, and every integer
point on the segment is one of those landings: a point A + t * (dx, dy) has
integer coordinates only when t is a multiple of 1/g, since the components
of the reduced step are coprime. So the answer is
gcd(|dx|, |dy|) + 1
the + 1 counting A itself. Note g is computed from DIFFERENCES, never from
the coordinates themselves.
## The degenerate case this problem settles
When A and B are the same point the segment is that single point, so the
answer is 1. The formula gives it for free, provided gcd(0, 0) is taken to
be 0: that is the convention the standard library uses in every language
offered here, and it is worth checking rather than assuming, because a
hand-written Euclid loop that starts with while b != 0 also returns 0 and a
version that divides first does not.
## Width
Coordinates satisfy |x|, |y| <= 1000000, so each difference is at most
2 * 10^6 and so is the answer. Nothing here overflows a 32-bit integer, which
is unusual in this topic and worth noticing: the quantity being computed is a
gcd of differences rather than a product of them.
Constraints - `1 <= q <= 100000` - `-1000000 <= ax, ay, bx, by <= 1000000` - `A` and `B` may be the same point, in which case the answer is 1
Input
The first line contains an integer q.
Each of the next q lines contains four integers ax ay bx by, the coordinates of A and B, separated by spaces.
Output
For each query print one integer on its own line, the number of points with integer coordinates on the closed segment from A to B, with nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.