Segment (Həll təhlili)

Əgər (x_1, y_1) və (x_2, y_2) - kəsiyin tam ədədi uclarıdırsa, onda kəsik üzərindəki tam ədədi nöqtələrin sayı ĤOD ( |x_2 - x_1|, |y_2 - y_1| ) + 1 bərabərdir.

Çünki kəsiyin uclarının koordinatları modulla 2 \cdot 10^9-dan çox deyil, onda koordinatlar arasındakı fərqin modulu |x_2 - x_1| və |y_2 - y_1| 4 \cdot 10^9-dən çox deyil. Məsələn, əgər x_1 = 2 \cdot 10^9 və x_2 = -2 \cdot 10^9, onda |x_2 - x_1| = 4 \cdot 10^9. Buna görə hesablamalarda $64$ bitlik tam ədəd tipindən istifadə olunmalıdır.

Nümunə

Birinci nümunə üçün cavab belədir

İkinci nümunə üçün cavab belədir

Alqoritmin həyata keçirilməsi

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq bölənini hesablayır.

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

Giriş məlumatlarını oxuyuruq.

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

Cavabı formulaya əsasən hesablayırıq və onu çıxarırıq.

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

Java həyata keçirilməsi

public class Main
{

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq bölənini hesablayır.

  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);

Giriş məlumatlarını oxuyuruq.

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

Cavabı formulaya əsasən hesablayırıq və onu çıxarırıq.

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

Python həyata keçirilməsi

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq bölənini hesablayır.

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)

Giriş məlumatlarını oxuyuruq.

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

Cavabı formulaya əsasən hesablayırıq və onu çıxarırıq.

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

Python həyata keçirilməsi — gcd

İki ədədin ƏOB-ni hesab etmək üçün Pythondakı gcd funksiyasından istifadə edəcəyik.

import math

Giriş məlumatlarını oxuyuruq.

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

Cavabı formulaya əsasən hesablayırıq və onu çıxarırıq.

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