Lattice Points on a Line

Problem Description

In the Cartesian plane, a parrot lives at every integer lattice point $(x,y)$ (where $x$ and $y$ are both integers).

A parrot wants to fly along a straight line segment from point $(x_1,y_1)$ to point $(x_2,y_2)$ (the two points are guaranteed to be distinct). How many integer lattice points lie strictly on this segment (excluding both endpoints), i.e. how many other parrots' homes will it pass on the way?

Input Format

One line with four integers $x_1,y_1,x_2,y_2$.

Output Format

One line with an integer: the number of lattice points passed.

Sample Input

1 1 5 7

Sample Output

1

Sample Explanation

The path passes through exactly one lattice point, $(3,4)$.

Data Range

All four integers lie in $[-10^9,10^9]$.

Hint

📚 Topic tag: this problem belongs to the combinatorial counting topic. It is not a loop problem and is placed here as optional material. If you have just started learning loops, feel free to skip it and come back when you have spare time.

Hint: the answer is related to the greatest common divisor of the differences in the x- and y-coordinates between the two points.