Redaksiya

Alqoritm Analizi

İki tam ədəd $a$ və $b$ -nin ən az ortaq kəsrəyi (LCM) hər ikisinə bölünən ən kiçik təbii ədəd adlanır. Məsələn, LCM(2, 3) = 6, LCM(6, 10) = 30.

Ən az ortaq kəsrəyi tapmaq üçün aşağıdakı düsturdan istifadə edirik:

GC D (a, b) * L CM (a, b) = a * b

Buradan

L CM (a, b) = \frac{a * b}{GC D ( a , b )}

$a$ , $b$ < $2 * 1 0^{9}$ olduğundan, $a * b$ dəyərinin vurulması zamanı int tipinin hədlərini aşa bilər. Hesablama zamanı long long tipindən istifadə etmək lazımdır.

Nümunə

Nümunədən olan ədədləri nəzərdən keçirək:

GC D (42, 24) * L CM (42, 24) = 42 * 24,

buradan

L CM (42, 24) = \frac{42 * 24}{GC D ( 42 , 24 )} = \frac{42 * 24}{6} = 168

Alqoritmin Tətbiqi

gcd (ən böyük ortaq bölən) və lcm (ən az ortaq kəsrəy) funksiyalarını tətbiq edin.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyun. Cavabı hesablayın və çıxış edin.

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

Python Tətbiqi

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

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