Redaksiya

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 realization

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

int gcd(int a, int 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(abs(x2 - x1), abs(y2 - y1)) + 1;
printf("%lld\n",res);

Java realization

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 realization

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 realization — 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)