İki natural ədədin ƏKOB-u#1602

İki natural ədədin ƏKOB-u (Həll təhlili)

Ən kiçik ortaq məxrəc (ƏOM) iki tam ədəd $a$ və $b$ -nin elə ən kiçik natural ədədidir ki, $a$ və $b$ -yə tam bölünür. Məsələn, $Ə O M (2, 3) = 6$ ƏOM(2, 3) = 6, $Ə O M (6, 10) = 30$ ƏOM(6, 10) = 30.

Ən kiçik ortaq məxrəci tapmaq üçün aşağıdakı formula istifadə edəcəyik:

Ə B O B (a, b) \cdot Ə O M (a, b) = a \cdot b,

ƏBOB(a, b) \cdot ƏOM(a, b) = a \cdot b,

buradan

Ə O M (a, b) = \frac{a \cdot b}{Ə B O B ( a , b )}

ƏOM(a, b) = \frac{a \cdot b}{ƏBOB(a, b)}

$a, b 0 ˘ 03 c 2 \cdot 1 0^{9}$ a, b \u003c 2 \cdot 10^9 olduğundan, $a \cdot b$ a \cdot b vurulanda int tipini aşmaq ehtimalı var. Hesablama zamanı long long tipindən istifadə edilməlidir.

Nümunə

Misaldakı ədədləri götürək:

Ə B O B (42, 24) \cdot Ə O M (42, 24) = 42 \cdot 24,

ƏBOB(42, 24) \cdot ƏOM(42, 24) = 42 \cdot 24,

buradan

Ə O M (42, 24) = \frac{42 \cdot 24}{Ə B O B ( 42 , 24 )} = \frac{42 \cdot 24}{6} = 168

ƏOM(42, 24) = \frac{42 \cdot 24}{ƏBOB(42, 24)} = \frac{42 \cdot 24}{6} = 168

Alqoritmin həyata keçirilməsi

gcd (ən böyük ortaq bölən) və lcm (ən kiçik ortaq məxrəc) funksiyalarını həyata keçirək.

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

long long lcm(long long a, long long b)
{
  return a / gcd(a, b) * b;
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%lld %lld", &a, &b);

İki ədədin ƏOM-ni hesablayır və çap edirik.

d = lcm(a, b);
printf("%lld\n", d);

Python həyata keçirilməsi

gcd (ən böyük ortaq bölən) və lcm (ən kiçik ortaq məxrəc) funksiyalarını həyata keçirək.

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)

def lcm(a, b):
  return a // gcd(a, b) * b

Python

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

a, b = map(int, input().split())

İki ədədin ƏOM-ni hesablayır və çap edirik.

print(lcm(a, b))

Python həyata keçirilməsi — lcm

İki ədədin ən kiçik ortaq məxrəcini (ƏOM) hesablamaq üçün Python dilindəki lcm funksiyasından istifadə edəcəyik.

import math

Giriş məlumatlarını oxuyuruq.

a, b = map(int, input().split())

İki ədədin ƏOM-ni hesablayır və çap edirik.

print(math.lcm(a, b))