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 دون باقٍ.

الدالة

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.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

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

الفكرة

الإجابة لا تقل عن العدد الأكبر. ابدأ بـ m عند max(a, b) وأضف 1 حتى يقسم العددين الناتج؛ أنت تجرّب المرشحين بترتيب تصاعدي، لذا فإن أول تطابق هو الأصغر. بالنسبة إلى 4 و6، تجرّب الأعداد من 6 إلى 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 و2 × big و3 × big، وتوقف عند أول عدد يقبل القسمة على العدد الأصغر. بالنسبة إلى 4 و6، تجرّب 6، ثم 12.

بما أن 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 × lcm = a × b. بالنسبة إلى 4 = 2² و6 = 2 × 3، يكون القاسم المشترك الأكبر هو 2 والمضاعف المشترك الأصغر هو 2² × 3 = 12.

تعثر خوارزمية إقليدس على القاسم المشترك الأكبر في 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 بخطأ)، رغم أن المضاعف المشترك الأصغر يقع ضمن النطاق.
القسمة باستخدام الأعداد ذات الفاصلة العائمة. قد تكون النتيجة 2.146654199E9 أو تفقد أرقامها الأخيرة؛ أبقِ كل شيء بأعداد صحيحة.
تشغيل حلقة إقليدس على a وb نفسيهما. بعد ذلك، يحتويان على القاسم المشترك الأكبر و0، لذا اعمل على نسخ منهما.
افتراض أن الإجابة هي a × b. يصح ذلك فقط عندما لا يشترك العددان في أي عامل: lcm(4, 6) تساوي 12، لا 24.

أسئلة شائعة3

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

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

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

باستخدام صيغة القاسم المشترك الأكبر، يكون الزمن 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 بت عندما تكون القائمة طويلة.

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

اختبار #1

اختبار #2

اختبار #3

الوسائط

a = 4
b = 6

الإخراج المتوقع

Least Common Multiple

الدالة

القيود

أمثلة

تلميحات

الحل

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

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

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

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

أسئلة شائعة3

مسائل مشابهة