Least Common Multiple

Q: İki sayının EKOK formülü nedir?

lcm(a, b) = a × b / gcd(a, b) , ara değer hiçbir zaman sonuçtan büyük olmayacak şekilde a / gcd(a, b) × b olarak hesaplanır. 4 ve 6 için gcd 2 'dir ve 4 / 2 × 6 = 12 .

Q: EKOK'u hesaplamanın zaman karmaşıklığı nedir?

OBEB formülüyle zaman karmaşıklığı O(log(min(a, b))) olur; bu, Öklid algoritmasının maliyetidir ve alan karmaşıklığı O(1) olur. Büyük sayının katları üzerinden ilerlemek O(min(a, b)) , birer birer saymak ise O(lcm(a, b)) karmaşıklığındadır.

Q: İkiden fazla sayının EKOK'unu nasıl bulursunuz?

Listeyi katlayın: lcm(a, b, c) = lcm(lcm(a, b), c) . [4, 6, 10] için lcm(4, 6) = 12 ve lcm(12, 10) = 60 . Biriken değer hızla büyür, bu nedenle liste uzunsa 64 bit tam sayılar kullanın.

BaşlangıçMatematik ve simülasyon

+10

İki pozitif tam sayı a ve b alırsın. Bunların en küçük ortak katını döndür: hem a hem de b tarafından kalansız bölünebilen en küçük pozitif tam sayı.

Fonksiyon

lcm(a: integer, b: integer) → integer

ainteger: ilk pozitif tam sayı
binteger: ikinci pozitif tam sayı
Döndürürinteger: hem a'nın hem de b'nin katı olan en küçük pozitif tam sayı

Kısıtlar

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
Yanıt, işaretli 32 bitlik bir tam sayıya sığar: lcm(a, b) ≤ 2³¹-1. a × b çarpımı sığmayabilir.

Örnekler

Girdi: a = 4b = 6
Çıktı: 12
Açıklama: 6'nın katları 6, 12, 18 diye başlar; 4'ün katları 4, 8, 12 diye başlar. Her iki listedeki ilk sayı 12'dir.

Girdi: a = 7b = 3
Çıktı: 21
Açıklama: 7 ve 3'ün 1 dışında ortak çarpanı yoktur, bu yüzden en küçük ortak katları çarpımları olan 21'dir.

Girdi: a = 15b = 45
Çıktı: 45
Açıklama: 15, 45'i kalansız böler; dolayısıyla 45 zaten her ikisinin de katıdır ve 45'in daha küçük bir katı yoktur.

Ek soru

Bölme ya da kalan işlemi hiç kullanmadan, yalnızca çıkarma ve ikiye bölme işlemlerini kullanarak EBOB'u bulabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

En küçük ortak kat ile en büyük ortak bölen şu gerçekle birbirine bağlıdır: gcd(a, b) × lcm(a, b) = a × b. Dolayısıyla hızlı yanıt a × b / gcd(a, b) olur. Çarpım 10^12 değerine ulaşabilir ve yanıt sığsa bile 32 bitlik bir tamsayıda taşmaya neden olabilir; bu nedenle çarpmadan önce EBOB'a bölün.

Büyük sayıdan başlayarak say

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Yanıt, büyük olan sayıdan en az o kadardır. m değerini max(a, b) olarak başlat ve her iki sayı da bu sayıyı kalansız bölene kadar 1 ekle; adayları artan sırayla denediğin için ilk bulunan en küçük sayıdır. 4 ve 6 için 6'dan 11'e kadar denersin ve 12 değerinde durursun. Döngü her zaman sona erer, çünkü a × b ortak bir kattır.

Deneme sayısı, yanıtın büyüklüğü kadardır. 46337 ve 46327 asal sayıları için yanıt 2146654199, yani iki milyardan fazla denemedir.

Algoritma

a ve b değerlerinden büyük olanı m olarak ayarla.
m % a veya m % b 0 değilken m değerini 1 artır.
m değerini döndür.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Daha büyük sayının katları arasında ilerleyin

Sezgi

Yanıt, büyük sayının big katı olmalı; bu yüzden big, 2 × big, 3 × big şeklinde ilerle ve küçük sayının böldüğü ilk sayıda dur. 4 ve 6 için önce 6'yı, sonra 12'yi denersin.

small × big her zaman ortak bir kat olduğundan, döngü en fazla min(a, b) kez çalışır; burada en fazla bir milyon kez. Bu sınırlar için yeterince hızlıdır, ancak girdiyle birlikte büyümeye devam eder; 10^18'e kadar sayılarla bu kadar hızlı olmazdı.

Algoritma

big büyük sayı, small ise küçük sayı olsun.
m = big olarak ayarla.
m % small değeri 0 olmadığı sürece m değerine big ekle.
m değerini döndür.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Önce EBOB’a bölün, sonra çarpın

Sezgi

Her iki sayıyı da asal çarpanlarına ayırın. Her asal sayı için EBOB, üslerinden küçük olanı; EKOK ise büyük olanı alır; böylece birlikte a ve b sayılarının tüm çarpanlarını tam olarak bir kez kullanırlar: gcd × lcm = a × b. 4 = 2² ve 6 = 2 × 3 için EBOB 2, EKOK ise 2² × 3 = 12 olur.

Öklid algoritması, EBOB'u O(log(min(a, b))) adımda bulur. Ardından a / gcd × b işlemini bu sırayla hesaplayın: EBOB, a sayısını tam böler; dolayısıyla hiçbir şey kaybolmaz ve hiçbir ara adım sonucu aşmaz. a = b = 10^6 olduğunda a × b / gcd işlemi 32 bitlik bir tamsayıda taşmaya neden olur; bu durumda çarpım 10^12, sonuç ise yalnızca 10^6 olur.

Algoritma

a ve b'yi x ve y'ye kopyalayın.
y 0 olmadığı sürece (x, y)'yi (y, x % y) ile değiştirin. Artık x EBOB'dur.
a'yı x'e bölün.
Sonucu b ile çarpın ve döndürün.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Tuzaklar ve uç durumlar

Önce a × b işlemini yapmak. Java, C, C++, C# ve Rust'ta 10^6 civarındaki iki sayının çarpımı 32 bitlik bir tamsayıyı taşır ve sonuç yanlış ya da negatif çıkar (Rust'ta hata ayıklama derlemesi panikler); oysa EKOK değeri sığar.
Kayan noktalı sayılarla bölme yapmak. Sonuç 2.146654199E9 olarak dönebilir veya son basamakları kaybolabilir; her şeyi tamsayılarla tutun.
Öklid algoritmasının döngüsünü doğrudan a ve b üzerinde çalıştırmak. Sonrasında bu değişkenler EBOB'u ve 0 değerini tutar; bu yüzden kopyalar üzerinde çalışın.
Yanıtın a × b olduğunu varsaymak. Bu yalnızca sayıların ortak çarpanı olmadığında geçerlidir: lcm(4, 6) değeri 24 değil, 12'dir.

Sıkça sorulan sorular3

İki sayının EKOK formülü nedir?

lcm(a, b) = a × b / gcd(a, b), ara değer hiçbir zaman sonuçtan büyük olmayacak şekilde a / gcd(a, b) × b olarak hesaplanır. 4 ve 6 için gcd 2'dir ve 4 / 2 × 6 = 12.

EKOK'u hesaplamanın zaman karmaşıklığı nedir?

OBEB formülüyle zaman karmaşıklığı O(log(min(a, b))) olur; bu, Öklid algoritmasının maliyetidir ve alan karmaşıklığı O(1) olur. Büyük sayının katları üzerinden ilerlemek O(min(a, b)), birer birer saymak ise O(lcm(a, b)) karmaşıklığındadır.

İkiden fazla sayının EKOK'unu nasıl bulursunuz?

Listeyi katlayın: lcm(a, b, c) = lcm(lcm(a, b), c). [4, 6, 10] için lcm(4, 6) = 12 ve lcm(12, 10) = 60. Biriken değer hızla büyür, bu nedenle liste uzunsa 64 bit tam sayılar kullanın.