Greatest Common Divisor

Q: ما هو التعقيد الزمني لخوارزمية إقليدس؟

يعمل في O(log(min(a, b))) خطوة، لأن العدد الأكبر ينخفض إلى النصف على الأقل كل خطوتين. أسوأ حالة هي زوج من أعداد فيبوناتشي المتتالية. بالنسبة إلى الأعداد حتى 10^9 ، لا يتجاوز ذلك 43 خطوة، وتستخدم الخوارزمية مساحة إضافية O(1) .

Q: لماذا يساوي gcd(a, b) ‏gcd(b, a % b)؟

اكتب a = q × b + r مع r = a % b . كل عدد يقسم a و b يقسم a - q × b ، وهو r . وكل عدد يقسم b و r يقسم q × b + r ، وهو a . للزوجين القواسم المشتركة نفسها، لذا لهما القاسم الأكبر نفسه.

مبتدئرياضيات ومحاكاة

+10

لديك عددان صحيحان موجبان a وb. أعد القاسم المشترك الأكبر لهما: أكبر عدد صحيح يقسم كليهما دون باقٍ.

على سبيل المثال، الأعداد التي تقسم كلًا من 8 و12 هي 1 و2 و4، لذا فالإجابة هي 4.

الدالة

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

ainteger: أول عدد صحيح موجب
binteger: العدد الصحيح الموجب الثاني
تُرجعinteger: أكبر عدد صحيح يقسم كلًا من a وb

القيود

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

أمثلة

المدخلات: a = 12b = 18
المخرجات: 6
الشرح: قواسم 12 هي 1 و2 و3 و4 و6 و12؛ وقواسم 18 هي 1 و2 و3 و6 و9 و18. أكبر عدد في كلتا القائمتين هو 6.

المدخلات: a = 17b = 5
المخرجات: 1
الشرح: كلٌّ من 17 و5 عدد أولي ومختلف عن الآخر، لذا فإن القاسم الوحيد المشترك بينهما هو 1.

المدخلات: a = 42b = 42
المخرجات: 42
الشرح: العدد يقسم نفسه، ولا يوجد عدد أكبر من 42 يمكنه قسمة 42، لذا فإن القاسم المشترك الأكبر لـ 42 و42 هو 42.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك توسيع خوارزمية إقليدس بحيث تُرجع أيضًا عددين صحيحين x وy بحيث يكون a × x + b × y = gcd(a, b)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يوحي التعريف بتجربة القيم المرشحة واحدةً تلو الأخرى، وهذا ينجح مع الأعداد الصغيرة. لكن عندما تصل قيمتا a وb إلى 10^9، فإن عددين كبيرين لا يشتركان في أي عامل يستلزمان مليار محاولة. لاحظ إقليدس أن gcd(a, b) يساوي gcd(b, a % b)، وهذا يقلّص الأعداد بسرعة كبيرة، بحيث لا يحتاج أي زوج من الأعداد حتى 10^9 إلى أكثر من 43 خطوة.

العد التنازلي بدءًا من العدد الأصغر

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

لا يمكن أن يكون أي قاسم مشترك أكبر من العدد الأصغر، لأن قاسم b لا يتجاوز b. لذا ابدأ بقيمة مرشحة d تساوي min(a, b) وأنقصها بمقدار واحد حتى تقسم العددين معًا. وبما أنك تجرّب القيم المرشحة بدءًا من الأكبر، فإن أول قيمة تنجح هي الأكبر.

بالنسبة إلى 12 و18، تجرّب 12 (لا يقسم 18)، ثم 11 و10 و9 و8 و7، وهي لا تنجح، وتتوقف عند 6. تنتهي الحلقة دائمًا، لأن 1 يقسم كل شيء.

التكلفة هي عدد القيم المرشحة. بالنسبة إلى 999999937 و999999929، وهما عددان أوليان، تكون الإجابة 1 وتُنفَّذ الحلقة نحو 10^9 مرة تقريبًا. وهذا بطيء جدًا بالنسبة إلى أكبر الاختبارات.

الخوارزمية

عيّن d لتكون الأصغر بين a وb.
ما دام a % d أو b % d لا يساوي 0، اطرح 1 من d.
أعِد d.

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

خوارزمية إقليدس

الفكرة

اكتب a = q × b + r، حيث r = a % b. أي عدد يقسم كلًا من a وb يقسم أيضًا r = a - q × b. وأي عدد يقسم كلًا من b وr يقسم أيضًا a = q × b + r. لذا فإن للزوجين (a, b) و(b, r) القواسم المشتركة نفسها تمامًا، وأكبرها واحد.

استبدل (a, b) بـ (b, a % b) وكرّر ذلك حتى تصبح b مساوية لـ 0. كل عدد يقسم 0، لذا فإن gcd(a, 0) = a، وتكون a هي الإجابة. بالنسبة إلى 12 و18: يتحول (12, 18) إلى (18, 12)، ثم (12, 6)، ثم (6, 0)، وتكون الإجابة 6. تبدّل الخطوة الأولى الأعداد تلقائيًا عندما تكون a أصغر، لذا لن تحتاج أبدًا إلى ترتيبها.

كل خطوتين على الأقل تُنصّفان العدد الأكبر، لذا تتكرر الحلقة O(log(min(a, b))) مرة. أبطأ المدخلات هي أعداد فيبوناتشي المتتالية مثل 701408733 و433494437، وحتى هذه لا تستغرق سوى 42 خطوة.

الخوارزمية

ما دام b لا يساوي 0، احسب r = a % b.
عيّن a = b وb = r.
عندما يصل b إلى 0، أعد a.

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

أخطاء شائعة وحالات حدّية

الخوارزمية قصيرة، لذا تنشأ الأخطاء من التحديث وشرط التوقف.

التحديث بالترتيب الخاطئ. يؤدي a = b متبوعًا بـ b = a % b إلى حساب b % b، وهي دائمًا 0، ثم إرجاع b. احفظ الباقي أولًا في متغير مؤقت، أو أسند القيمتين معًا.
إرجاع b بدلًا من a عند انتهاء الحلقة. عندها تكون قيمة b هي 0.
إيقاف العد التنازلي عند 2 أو البدء من max(a, b). يفوّت الخيار الأول أزواجًا أولية فيما بينها مثل 17 و5؛ أما الخيار الثاني فيهدر الوقت على قيم مرشحة لا يمكنها قسمة العدد الأصغر.
استخدام الطرح المتكرر بدلًا من الباقي. عندها يتطلب gcd(10^9, 1) مليار عملية طرح؛ أما % فينجزها كلها في خطوة واحدة.

أسئلة شائعة4

ما هو التعقيد الزمني لخوارزمية إقليدس؟

يعمل في O(log(min(a, b))) خطوة، لأن العدد الأكبر ينخفض إلى النصف على الأقل كل خطوتين. أسوأ حالة هي زوج من أعداد فيبوناتشي المتتالية. بالنسبة إلى الأعداد حتى 10^9، لا يتجاوز ذلك 43 خطوة، وتستخدم الخوارزمية مساحة إضافية O(1).

لماذا يساوي gcd(a, b) ‏gcd(b, a % b)؟

اكتب a = q × b + r مع r = a % b. كل عدد يقسم a وb يقسم a - q × b، وهو r. وكل عدد يقسم b وr يقسم q × b + r، وهو a. للزوجين القواسم المشتركة نفسها، لذا لهما القاسم الأكبر نفسه.

ما الفرق بين القاسم المشترك الأكبر والمضاعف المشترك الأصغر؟

القاسم المشترك الأكبر هو أكبر عدد يقسم كلا المدخلين؛ والمضاعف المشترك الأصغر هو أصغر عدد يقبل القسمة عليه من كلا المدخلين. ويرتبطان بالعلاقة gcd(a, b) × lcm(a, b) = a × b، لذا بمجرد إيجاد القاسم المشترك الأكبر، يكون المضاعف المشترك الأصغر هو a / gcd(a, b) × b.

ما هو القاسم المشترك الأكبر لعددين أوليين فيما بينهما؟

يكون عددان أوليين فيما بينهما عندما يكون القاسم المشترك الأكبر لهما هو 1، أي إنهما لا يشتركان في أي عامل أولي. وكل عددين أوليين مختلفين أوليان فيما بينهما دائمًا، وكذلك أي عددين صحيحين متتاليين، مثل 8 و9.

Python

def gcd(a, b):
    # اكتب الشيفرة هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

a = 12
b = 18

المتوقع