The Segment (Editorial)

If (x_1, y_1) and (x_2, y_2) are integer endpoints of the segment, then the number of integer points on it is equal to GCD ( |x_2 - x_1|, |y_2 - y_1| ) + 1.

Since the coordinates of the segment endpoints do not exceed 2 \cdot 10^9 in absolute value, the absolute difference of coordinates |x_2 - x_1| and |y_2 - y_1| does not exceed 4 \cdot 10^9. For example, if x_1 = 2 \cdot 10^9 and x_2 = -2 \cdot 10^9, then |x_2 - x_1| = 4 \cdot 10^9. Therefore, $64$-bit integer type should be used for computations.

Example

For the first example, the answer is

For the second example, the answer is

Algorithm implementation

The gcd function returns the greatest common divisor of the numbers $a$ and $b$.

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

Read the input data.

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);

Compute the answer using the formula and print it.

res = gcd(labs(x2 - x1), labs(y2 - y1)) + 1;
printf("%lld\n",res);

Java implementation

public class Main
{

The gcd function returns the greatest common divisor of the numbers $a$ and $b$.

  static long gcd(long a, long b)
  {
    if (b == 0) return a;
    return gcd(b,a % b);
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);

Read the input data.

    long x1 = con.nextLong(),
         y1 = con.nextLong(),
         x2 = con.nextLong(),
         y2 = con.nextLong();

Compute the answer using the formula and print it.

    long res = 1 + gcd(Math.abs(x2 - x1), Math.abs(y2 - y1));
    System.out.println(res);
  }
}

Python implementation

The gcd function returns the greatest common divisor of the numbers $a$ and $b$.

def gcd(a, b):
  if a == 0: return b
  if b == 0: return a
  if a > b: return gcd(a % b, b)
  return gcd(a, b % a)

Read the input data.

x1, y1, x2, y2 = map(int, input().split())

Compute the answer using the formula and print it.

res = gcd(abs(x2 - x1), abs(y2 - y1)) + 1
print(res)

Python implementation — gcd

To compute the greatest common divisor (GCD) of two numbers, let's use the gcd function built into the Python language.

import math

Read the input data.

x1, y1, x2, y2 = map(int, input().split())

Compute the answer using the formula and print it.

res = math.gcd(abs(x2 - x1), abs(y2 - y1)) + 1
print(res)