Відрізок (Розбір)

Якщо (x_1, y_1) і (x_2, y_2) — цілочисельні кінці відрізка, то кількість цілочисельних точок на ньому дорівнює НОД ( |x_2 - x_1|, |y_2 - y_1| ) + 1.

Оскільки координати кінців відрізка за модулем не перевищують 2 \cdot 10^9, то модуль різниці координат |x_2 - x_1| і |y_2 - y_1| не перевищує 4 \cdot 10^9. Наприклад, якщо x_1 = 2 \cdot 10^9 і x_2 = -2 \cdot 10^9, то |x_2 - x_1| = 4 \cdot 10^9. Тому при обчисленнях слід скористатися $64$ бітовим цілочисельним типом.

Приклад

Для першого прикладу відповідь дорівнює

Для другого прикладу відповідь дорівнює

Реалізація алгоритму

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $b$.

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

Читаємо вхідні дані.

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

Обчислюємо відповідь за формулою і виводимо її.

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

Java реалізація

public class Main
{

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $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);

Читаємо вхідні дані.

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

Обчислюємо відповідь за формулою і виводимо її.

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

Python реалізація

Функція gcd обчислює найбільший спільний дільник чисел $a$ і $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)

Читаємо вхідні дані.

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

Обчислюємо відповідь за формулою і виводимо її.

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

Python реалізація — gcd

Для обчислення НОД двох чисел скористаємося функцією gcd, вбудованою в мові Пітон.

import math

Читаємо вхідні дані.

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

Обчислюємо відповідь за формулою і виводимо її.

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