Greatest Common Divisor

Q: Öklid algoritmasının zaman karmaşıklığı nedir?

O(log(min(a, b))) adımda çalışır; çünkü her iki adımda bir büyük sayı en az yarıya iner. En kötü durum, ardışık iki Fibonacci sayısından oluşan bir çifttir. 10^9 'a kadar olan sayılar için bu en fazla 43 adımdır ve algoritma O(1) ek alan kullanır.

Q: gcd(a, b) neden gcd(b, a % b)'ye eşittir?

a = q × b + r ifadesini r = a % b olacak şekilde yazın. a ve b sayılarını bölen bir sayı, a - q × b ifadesini de böler; bu da r 'dir. b ve r sayılarını bölen bir sayı, q × b + r ifadesini de böler; bu da a 'dır. Her iki çiftin ortak bölenleri aynıdır, dolayısıyla en büyük ortak bölenleri de aynıdır.

Q: Aralarında asal iki sayının EBOB'u nedir?

İki sayının en büyük ortak böleni 1 olduğunda, yani ortak asal çarpanları olmadığında bu sayılar aralarında asaldır. Farklı iki asal sayı ve 8 ile 9 gibi ardışık iki tam sayı her zaman aralarında asaldır.

BaşlangıçMatematik ve simülasyon

+10

İki pozitif tam sayı a ve b alırsınız. Her ikisini de kalansız bölen en büyük tam sayı olan en büyük ortak bölenlerini döndürün.

Örneğin, hem 8 hem de 12 sayısını bölen sayılar 1, 2 ve 4 olduğundan yanıt 4 olur.

Fonksiyon

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

ainteger: ilk pozitif tam sayı
binteger: ikinci pozitif tam sayı
Döndürürinteger: hem a'yı hem de b'yi bölen en büyük tam sayı

Kısıtlar

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Örnekler

Girdi: a = 12b = 18
Çıktı: 6
Açıklama: 12 sayısının bölenleri 1, 2, 3, 4, 6 ve 12'dir; 18 sayısının bölenleri 1, 2, 3, 6, 9 ve 18'dir. Her iki listedeki en büyük sayı 6'dır.

Girdi: a = 17b = 5
Çıktı: 1
Açıklama: 17 ve 5 asal ve birbirinden farklıdır, bu nedenle ortak bölenleri yalnızca 1'dir.

Girdi: a = 42b = 42
Çıktı: 42
Açıklama: Bir sayı kendisini böler ve 42'den büyük hiçbir sayı 42'yi bölemez; bu nedenle 42 ile 42'nin en büyük ortak böleni 42'dir.

Gönderirken +14 gizli test

Ek soru

Öklid algoritmasını, a × x + b × y = gcd(a, b) eşitliğini sağlayan x ve y tam sayılarını da döndürecek şekilde genişletebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Tanım, adayları teker teker denemeyi öneriyor ve bu küçük sayılarda işe yarıyor. Ancak a ve b en fazla 10^9 olduğunda, ortak çarpanı olmayan iki büyük sayı bir milyar deneme gerektirir. Öklid'in gcd(a, b) değerinin gcd(b, a % b) değerine eşit olduğu gözlemi, sayıları o kadar hızlı küçültür ki 10^9'a kadar hiçbir sayı çifti 43 adımdan fazlasını gerektirmez.

Küçük sayıdan geri say

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

Sezgi

Ortak bir bölen, iki sayıdan küçüğünden büyük olamaz; çünkü b sayısının bir böleni en fazla b olabilir. Bu yüzden aday d değerini min(a, b) olarak başlat ve her ikisini de bölene kadar birer birer azalt. Adayları en büyükten başlayarak denediğin için, işe yarayan ilk aday en büyük olandır.

12 ve 18 için 12'yi (18'i bölmez), ardından 11, 10, 9, 8 ve 7'yi denersin; bunlar işe yaramaz ve 6'da durursun. 1 her sayıyı böldüğü için döngü her zaman sona erer.

Maliyet, adayların sayısıdır. İki asal sayı olan 999999937 ve 999999929 için yanıt 1'dir ve döngü neredeyse 10^9 kez çalışır. Bu, en büyük testler için çok yavaştır.

Algoritma

d değerini a ve b değerlerinden küçük olana ayarlayın.
a % d veya b % d değeri 0 değilken d değerinden 1 çıkarın.
d değerini döndürün.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Öklid algoritması

Sezgi

a = q × b + r yazın; burada r = a % b. Hem a hem de b sayısını bölen herhangi bir sayı, r = a - q × b sayısını da böler. Hem b hem de r sayısını bölen herhangi bir sayı da a = q × b + r sayısını böler. Dolayısıyla (a, b) ve (b, r) çiftlerinin ortak bölenleri ve en büyük ortak bölenleri aynıdır.

(a, b) çiftini (b, a % b) ile değiştirin ve b 0 olana kadar tekrarlayın. Her sayı 0’ı böldüğünden, gcd(a, 0) = a olur ve yanıt a’dır. 12 ve 18 için: (12, 18), (18, 12) olur; ardından (12, 6), sonra da (6, 0) olur ve yanıt 6’dır. İlk adım, a daha küçük olduğunda sayıları kendiliğinden yer değiştirir; bu yüzden onları sıralamanız gerekmez.

Her iki adımda büyük sayı en az yarıya iner, dolayısıyla döngü O(log(min(a, b))) kez çalışır. En yavaş girdiler, 701408733 ve 433494437 gibi ardışık Fibonacci sayılarıdır; onlar bile yalnızca 42 adım sürer.

Algoritma

b 0 olmadığı sürece r = a % b hesapla.
a = b ve b = r olarak ayarla.
b 0 olduğunda a değerini döndür.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Tuzaklar ve uç durumlar

Algoritma kısadır; bu nedenle hatalar güncelleme işleminden ve durdurma koşulundan kaynaklanır.

Yanlış sırayla güncelleme yapmak. a = b işleminin ardından b = a % b işlemini yapmak, her zaman 0 olan b % b sonucunu hesaplar ve b değerini döndürür. Kalanı önce geçici bir değişkene kaydedin veya ikisini aynı anda atayın.
Döngü bittiğinde a yerine b değerini döndürmek. O noktada b, 0 değerindedir.
Geri sayımı 2 değerinde durdurmak veya sayımı max(a, b) değerinden başlatmak. İlki, 17 ve 5 gibi aralarında asal olan çiftleri kaçırır; ikincisi, küçük sayıyı bölemeyecek adaylarla zaman kaybettirir.
Kalanı kullanmak yerine art arda çıkarma yapmak. Bu durumda gcd(10^9, 1) için bir milyar çıkarma işlemi gerekir; % ise bunların hepsini tek adımda yapar.

Sıkça sorulan sorular4

Öklid algoritmasının zaman karmaşıklığı nedir?

O(log(min(a, b))) adımda çalışır; çünkü her iki adımda bir büyük sayı en az yarıya iner. En kötü durum, ardışık iki Fibonacci sayısından oluşan bir çifttir. 10^9'a kadar olan sayılar için bu en fazla 43 adımdır ve algoritma O(1) ek alan kullanır.

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

a = q × b + r ifadesini r = a % b olacak şekilde yazın. a ve b sayılarını bölen bir sayı, a - q × b ifadesini de böler; bu da r'dir. b ve r sayılarını bölen bir sayı, q × b + r ifadesini de böler; bu da a'dır. Her iki çiftin ortak bölenleri aynıdır, dolayısıyla en büyük ortak bölenleri de aynıdır.

GCD ile LCM arasındaki fark nedir?

En büyük ortak bölen, her iki girdiyi de bölen en büyük sayıdır; en küçük ortak kat ise her iki girdinin de böldüğü en küçük sayıdır. Aralarındaki ilişki gcd(a, b) × lcm(a, b) = a × b şeklindedir; bu nedenle EBOB'u bulduğunuzda EKOK a / gcd(a, b) × b olur.

Aralarında asal iki sayının EBOB'u nedir?

İki sayının en büyük ortak böleni 1 olduğunda, yani ortak asal çarpanları olmadığında bu sayılar aralarında asaldır. Farklı iki asal sayı ve 8 ile 9 gibi ardışık iki tam sayı her zaman aralarında asaldır.