Least Common Multiple

Q: ما صيغة المضاعف المشترك الأصغر لعددين؟

lcm(a, b) = a × b / gcd(a, b) ، ويُحسب على النحو التالي: a / gcd(a, b) × b حتى لا تتجاوز القيمة الوسيطة الناتج أبدًا. بالنسبة إلى 4 و 6 ، يكون القاسم المشترك الأكبر هو 2 ، و 4 / 2 × 6 = 12 .

Q: ما هو التعقيد الزمني لحساب المضاعف المشترك الأصغر؟

باستخدام صيغة القاسم المشترك الأكبر، يكون التعقيد O(log(min(a, b))) ، وهو تكلفة خوارزمية إقليدس، بالإضافة إلى عملية قسمة واحدة وعملية ضرب واحدة. وتحتاج إلى مساحة إضافية O(1) . البحث عبر المضاعفات أبطأ بكثير: O(min(a, b)) عند التقدّم بمقدار العدد الأكبر، و O(lcm(a, b)) عند العدّ بمقدار واحد.

Q: كيف تجد المضاعف المشترك الأصغر لأكثر من عددين؟

اطوِ القائمة: lcm(a, b, c) = lcm(lcm(a, b), c) . بالنسبة إلى [4, 6, 10] ، فإن lcm(4, 6) = 12 و lcm(12, 10) = 60 . تزداد القيمة المتراكمة بسرعة، لذا انتبه إلى تجاوز السعة واستخدم أعدادًا صحيحة من 64 بت عندما تكون القائمة طويلة.

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

+10

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

على سبيل المثال، مضاعفات 6 هي 6 و12 و18 و24 وما إلى ذلك، ومضاعفات 8 هي 8 و16 و24 وما إلى ذلك، وأول عدد يظهر في القائمتين هو 24.

الدالة

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

ainteger: أول عدد صحيح موجب
binteger: العدد الصحيح الموجب الثاني
تُرجعinteger: أصغر عدد صحيح موجب من مضاعفات كلٍّ من a وb

القيود

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
الإجابة تقع ضمن نطاق عدد صحيح موقّع ذي 32 بت: lcm(a, b) ≤ 2³¹-1. قد لا يكون حاصل الضرب a × b كذلك.

أمثلة

المدخلات: a = 4b = 6
المخرجات: 12
الشرح: مضاعفات 6 تبدأ بـ 6، 12، 18؛ ومضاعفات 4 تبدأ بـ 4، 8، 12. العدد الأول في كلتا القائمتين هو 12.

المدخلات: a = 7b = 3
المخرجات: 21
الشرح: لا يشترك 7 و3 في أي عامل سوى 1، لذا فإن المضاعف المشترك الأصغر لهما هو حاصل ضربهما، 21.

المدخلات: a = 15b = 45
المخرجات: 45
الشرح: 15 يقسم 45 دون باقٍ، لذا فإن 45 هو بالفعل مضاعف لكليهما، ولا يوجد مضاعف أصغر من 45.

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

سؤال إضافي

هل يمكنك إيجاد القاسم المشترك الأكبر دون استخدام القسمة أو باقي القسمة إطلاقًا، باستخدام الطرح والتنصيف فقط؟

تلميحات

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

فُتح 0 من 3

الحل

المضاعف المشترك الأصغر والقاسم المشترك الأكبر هما وجهان لحقيقة واحدة: gcd(a, b) × lcm(a, b) = a × b. لذا فالإجابة السريعة هي a × b / gcd(a, b)، مع وجود مشكلة واحدة. قد يصل حاصل الضرب إلى 10^12، وهذا يتجاوز سعة عدد صحيح ذي 32 بت حتى عندما تكون الإجابة ضمن النطاق، لذا اقسم على القاسم المشترك الأكبر قبل أن تضرب.

عُدّ تصاعديًا بدءًا من العدد الأكبر

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

الفكرة

الإجابة من مضاعفات كلا العددين، لذا فهي لا تقل عن الأكبر منهما. ابدأ المرشح m عند max(a, b) وأضف 1 حتى يقسمها كلٌّ من a وb. تجرّب المرشحين بترتيب تصاعدي، لذا فإن أول مرشح ينجح هو الأصغر.

بالنسبة إلى 4 و6، تجرّب 6 و7 و8 و9 و10 و11، وتفشل هذه المرشحات، ثم تتوقف عند 12. تنتهي الحلقة دائمًا، لأن a × b من المضاعفات المشتركة.

عدد المحاولات يقارب حجم الإجابة. بالنسبة إلى 46337 و46327، وهما عددان أوليان، تكون الإجابة 2146654199، لذا تتكرر الحلقة أكثر من ملياري مرة. وهذا بطيء جدًا.

الخوارزمية

اجعل m يساوي الأكبر بين a وb.
ما دام m % a أو m % b لا يساوي 0، أضف 1 إلى m.
أعِد m.

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

تقدّم عبر مضاعفات العدد الأكبر

الفكرة

معظم المرشّحات في العدّ غير مجدية: يجب أن تكون الإجابة من مضاعفات العدد الأكبر، ولنسمّه big. لذا انتقل مباشرةً من مضاعف لـ big إلى المضاعف التالي، big، 2 × big، 3 × big، وتوقّف عند أول مضاعف يقسمه العدد الأصغر.

بالنسبة إلى 4 و6، تجرّب 6 (لا يقسمه 4)، ثم 12 (يقسمه). الإجابة هي k × big لقيمة ما لـ k، وتكون k على الأكثر مساوية للعدد الأصغر، لأن small × big هو دائمًا مضاعف مشترك. لذا تنفّذ الحلقة min(a, b) تكرارًا على الأكثر، وهذا لا يتجاوز مليونًا في هذه الحالة.

هذا سريع بما يكفي هنا، لكنه يظل يزداد مع حجم المدخلات. أما مع أعداد تصل إلى 10^18، فلن يكون سريعًا بما يكفي.

الخوارزمية

ليكن big العدد الأكبر وsmall العدد الأصغر.
عيّن m = big.
ما دام m % small لا يساوي 0، أضف big إلى m.
أعِد m.

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

اقسم على القاسم المشترك الأكبر، ثم اضرب

الفكرة

حلّل كلا العددين إلى عواملهما الأولية. تأخذ القاسم المشترك الأكبر كلَّ عامل أولي بأصغر أسّ من أسّيه، ويأخذ المضاعف المشترك الأصغر أكبرهما، ويستخدمان معًا كلَّ عامل من a ومن b مرة واحدة بالضبط. وهذا يعطي gcd(a, b) × lcm(a, b) = a × b، وبالتالي lcm(a, b) = a × b / gcd(a, b). بالنسبة إلى 4 = 2² و6 = 2 × 3، القاسم المشترك الأكبر هو 2 والمضاعف المشترك الأصغر هو 2² × 3 = 12.

أوجد القاسم المشترك الأكبر باستخدام خوارزمية إقليدس: استبدل (x, y) بـ (y, x % y) حتى يصبح y مساويًا لـ 0. يستغرق ذلك O(log(min(a, b))) خطوة.

ثم احسب a / gcd × b، بهذا الترتيب. يقسم القاسم المشترك الأكبر a دون باقٍ، لذا لا يفقد الناتج شيئًا، ولا تتجاوز النتيجة الإجابة أبدًا. إن كتابة a × b / gcd بدلًا من ذلك تؤدي إلى تجاوز سعة عدد صحيح ذي 32 بتًا عندما يكون a = b = 10^6: حاصل الضرب هو 10^12، بينما الإجابة لا تتجاوز 10^6.

الخوارزمية

انسخ a وb إلى x وy.
ما دام y لا يساوي 0، استبدل (x, y) بـ (y, x % y). الآن x هو القاسم المشترك الأكبر.
اقسم a على x.
اضرب الناتج في b وأعِده.

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

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

الصيغة في سطر واحد، والأخطاء تكمن في ترتيب العمليات الحسابية.

حساب a × b أولًا. في Java وC وC++ وC# وRust، يؤدي حاصل ضرب عددين قريبين من 10^6 إلى تجاوز سعة عدد صحيح ذي 32 بت، فتكون الإجابة خاطئة أو سالبة (أما إصدار التصحيح في Rust فيتوقف بخطأ)، مع أن القيمة الصحيحة للمضاعف المشترك الأصغر تقع ضمن النطاق.
قسمة a × b على القاسم المشترك الأكبر باستخدام الأعداد ذات الفاصلة العائمة. قد تكون النتيجة 2.146654199E9 أو تفقد أرقامها الأخيرة؛ استخدم الأعداد الصحيحة في جميع العمليات.
تنفيذ حلقة إقليدس على a وb نفسيهما، ثم استخدامهما في الصيغة. بعد انتهاء الحلقة، تصبح قيمتاهما القاسم المشترك الأكبر و0، لذا أجرِ العمليات على نسختين منهما.
افتراض أن الإجابة هي a × b. يصح ذلك فقط عندما لا يشترك العددان في أي عامل: lcm(4, 6) يساوي 12، وليس 24.

أسئلة شائعة4

ما صيغة المضاعف المشترك الأصغر لعددين؟

lcm(a, b) = a × b / gcd(a, b)، ويُحسب على النحو التالي: a / gcd(a, b) × b حتى لا تتجاوز القيمة الوسيطة الناتج أبدًا. بالنسبة إلى 4 و6، يكون القاسم المشترك الأكبر هو 2، و4 / 2 × 6 = 12.

لماذا يساوي gcd(a, b) × lcm(a, b) حاصل ضرب a × b؟

لكل عدد أولي، يستخدم القاسم المشترك الأكبر الأصغرَ من أسّه في a وb، بينما يستخدم المضاعف المشترك الأصغر الأكبرَ منهما. مجموع الأصغر والأكبر هو مجموع الأسّين، وهذا يساوي تمامًا أسّ ذلك العدد الأولي في a × b. ينطبق ذلك على كل الأعداد الأولية، لذا فإن حاصلَي الضرب متساويان.

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

باستخدام صيغة القاسم المشترك الأكبر، يكون التعقيد O(log(min(a, b)))، وهو تكلفة خوارزمية إقليدس، بالإضافة إلى عملية قسمة واحدة وعملية ضرب واحدة. وتحتاج إلى مساحة إضافية O(1). البحث عبر المضاعفات أبطأ بكثير: O(min(a, b)) عند التقدّم بمقدار العدد الأكبر، وO(lcm(a, b)) عند العدّ بمقدار واحد.

كيف تجد المضاعف المشترك الأصغر لأكثر من عددين؟

اطوِ القائمة: lcm(a, b, c) = lcm(lcm(a, b), c). بالنسبة إلى [4, 6, 10]، فإن lcm(4, 6) = 12 وlcm(12, 10) = 60. تزداد القيمة المتراكمة بسرعة، لذا انتبه إلى تجاوز السعة واستخدم أعدادًا صحيحة من 64 بت عندما تكون القائمة طويلة.

Python

def lcm(a, b):
    # اكتب الكود هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

a = 4
b = 6

المتوقع

Least Common Multiple

الدالة

القيود

أمثلة

تلميحات

الحل

عُدّ تصاعديًا بدءًا من العدد الأكبر

تقدّم عبر مضاعفات العدد الأكبر

اقسم على القاسم المشترك الأكبر، ثم اضرب

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

أسئلة شائعة4

مسائل مشابهة