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: gcd(a, b) × lcm(a, b) neden a × b'ye eşittir?

Her asal sayı için EBOB, a ve b içindeki kuvvetlerden küçüğünü, EKOK ise büyüğünü kullanır. Küçük ve büyük kuvvetin toplamı, her iki kuvvetin toplamıdır ve bu da söz konusu asal sayının a × b içindeki kuvvetine tam olarak eşittir. Her asal sayı eşleştiğinden, iki çarpım eşittir.

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

Listeyi katla: 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 yüzden taşmaya dikkat et ve liste uzun olduğunda 64 bit tam sayılar kullan.

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ı.

Örneğin, 6 sayısının katları 6, 12, 18, 24 ve böyle devam eder; 8 sayısının katları 8, 16, 24 ve böyle devam eder ve her iki listedeki ilk sayı 24 olur.

Fonksiyon

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

ainteger: ilk pozitif tam sayı
binteger: ikinci pozitif tam sayı
Döndürürinteger: a ve b'nin her ikisinin de 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 nedenle en küçük ortak katları çarpımları olan 21'dir.

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

Gönderirken +15 gizli test

Ek soru

Bölme ya da kalan işlemi hiç kullanmadan, yalnızca çıkarma ve ikiye bölme işlemleriyle 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 ve en büyük ortak bölen, tek bir gerçeğin iki yüzüdür: gcd(a, b) × lcm(a, b) = a × b. Dolayısıyla hızlı yanıt a × b / gcd(a, b) olur; ancak bir püf noktası var. Çarpım 10^12 değerine ulaşabilir ve yanıt bu sınıra sığsa bile 32 bitlik bir tamsayıyı taşırabilir. Bu nedenle çarpmadan önce EBOB'a bölersin.

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

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

Sezgi

Yanıt her iki sayının da katıdır, bu yüzden en büyüklerinden en az onun kadar büyüktür. Aday m değerini max(a, b) olarak başlat ve hem a hem de b bu sayıyı kalansız bölene kadar 1 ekle. Adayları artan sırayla denersin, bu yüzden işe yarayan ilk aday en küçüğüdür.

4 ve 6 için 6, 7, 8, 9, 10 ve 11'i denersin; bunlar başarısız olur ve 12'de durursun. a × b ortak bir kat olduğundan döngü her zaman sona erer.

Deneme sayısı yanıtın büyüklüğüyle yaklaşık olarak orantılıdır. İki asal sayı olan 46337 ve 46327 için yanıt 2146654199 olur; bu nedenle döngü iki milyardan fazla kez çalışır. Bu çok yavaştır.

Algoritma

a ve b değerlerinden büyük olanı m'ye ata.
m % a veya m % b 0 olmadığı sürece m'ye 1 ekle.
m'yi döndür.

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

Büyük sayının katları arasında ilerleyin

Sezgi

Sayımda yer alan adayların çoğu işe yaramaz: cevap, büyük sayının katı olmalıdır; bu sayıya big diyelim. Bu yüzden doğrudan bir big katından sonrakine geç: big, 2 × big, 3 × big ve küçük sayı ilk kez böldüğünde dur.

4 ve 6 için 6'yı denersin (4 onu bölmez), ardından 12'yi denersin (böler). Cevap, bir k değeri için k × big olur ve k, küçük sayıdan büyük olamaz; çünkü small × big her zaman ortak bir kattır. Dolayısıyla döngü en fazla min(a, b) kez çalışır; bu da burada hiçbir zaman bir milyondan fazla değildir.

Burada bu yeterince hızlıdır, ancak yine de girdiyle birlikte büyür. 10^18'e kadar olan sayılarla bu yöntem yeterli 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, sonra çarp

Sezgi

Her iki sayıyı da asal çarpanlarına ayırın. EBOB, her asal çarpanı iki kuvvetinden küçük olanıyla; EKOK ise büyük olanıyla alır ve birlikte a ile b sayılarının tüm çarpanlarını tam olarak bir kez kullanırlar. Böylece gcd(a, b) × lcm(a, b) = a × b elde edilir; dolayısıyla lcm(a, b) = a × b / gcd(a, b). 4 = 2² ve 6 = 2 × 3 için EBOB 2, EKOK ise 2² × 3 = 12 olur.

Öklid algoritmasıyla EBOB'u bulun: y değeri 0 olana kadar (x, y) çiftini (y, x % y) ile değiştirin. Bu işlem O(log(min(a, b))) adım sürer.

Ardından a / gcd × b işlemini bu sırayla hesaplayın. EBOB, a sayısını kalansız böler; dolayısıyla bölme hiçbir değer kaybına yol açmaz ve sonuç hiçbir zaman yanıttan büyük olmaz. Bunun yerine a × b / gcd yazmak, a = b = 10^6 için 32 bitlik bir tamsayıda taşmaya neden olur: çarpım 10^12 iken yanıt 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

Formül tek satırdan oluşur ve hatalar aritmetik işlemlerin sırasından kaynaklanır.

Önce a × b değerini hesaplamak. Java, C, C++, C# ve Rust'ta 10^6 civarındaki iki sayının çarpımı 32 bitlik bir tamsayıyı taşırır ve gerçek lcm sığmasına rağmen sonuç yanlış veya negatif çıkar (Rust'ta hata ayıklama derlemesi bunun yerine paniğe yol açar).
a × b değerini gcd'ye kayan noktalı sayılarla bölmek. Sonuç 2.146654199E9 olarak dönebilir veya son basamaklarını kaybedebilir; her şeyi tamsayı olarak tut.
Euclid döngüsünü doğrudan a ve b üzerinde çalıştırıp sonra bunları formülde kullanmak. Döngüden sonra bu değişkenlerde gcd ve 0 bulunur; bu yüzden kopyalar üzerinde çalış.
Sonucun a × b olduğunu varsaymak. Bu yalnızca iki sayının ortak çarpanı olmadığında geçerlidir: lcm(4, 6) değeri 24 değil, 12'dir.

Sıkça sorulan sorular4

İ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.

gcd(a, b) × lcm(a, b) neden a × b'ye eşittir?

Her asal sayı için EBOB, a ve b içindeki kuvvetlerden küçüğünü, EKOK ise büyüğünü kullanır. Küçük ve büyük kuvvetin toplamı, her iki kuvvetin toplamıdır ve bu da söz konusu asal sayının a × b içindeki kuvvetine tam olarak eşittir. Her asal sayı eşleştiğinden, iki çarpım eşittir.

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

gcd formülüyle maliyet, Euclid algoritmasının maliyeti olan O(log(min(a, b))) ile bir bölme ve bir çarpma işlemidir. O(1) ek alan gerektirir. Katları aramak çok daha yavaştır: büyük sayı kadar artırarak ilerlediğinizde O(min(a, b)), birer birer saydığınızda ise O(lcm(a, b)).

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

Listeyi katla: 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 yüzden taşmaya dikkat et ve liste uzun olduğunda 64 bit tam sayılar kullan.