Least Common Multiple

Q: מהי הנוסחה למציאת הכפולה המשותפת הקטנה ביותר של שני מספרים?

lcm(a, b) = a × b / gcd(a, b) , מחושב כך: a / gcd(a, b) × b , כדי שאף ערך ביניים לא יעלה על התוצאה. עבור 4 ו־ 6 , ה־gcd הוא 2 , ו־ 4 / 2 × 6 = 12 .

Q: מהי סיבוכיות הזמן של חישוב ה־LCM?

בעזרת נוסחת ה־gcd, זמן הריצה הוא 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

חלקו ב־gcd, ואז הכפילו

האינטואיציה

פרק את שני המספרים לגורמים ראשוניים. עבור כל מספר ראשוני, ה־gcd לוקח את החזקה הקטנה יותר מבין השתיים שלו, וה־lcm את הגדולה יותר, כך שביחד הם משתמשים בכל גורם של a ושל b בדיוק פעם אחת: gcd × lcm = a × b. עבור 4 = 2² ו־6 = 2 × 3, ה־gcd הוא 2 וה־lcm הוא 2² × 3 = 12.

האלגוריתם של אוקלידס מוצא את ה־gcd ב־O(log(min(a, b))) צעדים. לאחר מכן חשב את a / gcd × b בסדר הזה: ה־gcd מחלק את 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 הוא ה-gcd.
חלק את 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 סיביות ומתקבלת שגויה או שלילית (ב-build לניפוי שגיאות של Rust מתרחשת קריסה), אף שה-LCM נכנס לטווח.
חלוקה בנקודה צפה. התוצאה עלולה להתקבל בתור 2.146654199E9 או לאבד את הספרות האחרונות שלה; יש להשאיר הכול במספרים שלמים.
הרצת לולאת אוקלידס על a ועל b עצמם. לאחר מכן הם מכילים את ה-GCD ואת 0, לכן יש לעבוד על עותקים.
הנחה שהתשובה היא a × b. זה נכון רק כשהמספרים אינם חולקים גורם משותף: lcm(4, 6) הוא 12, ולא 24.

שאלות נפוצות3

מהי הנוסחה למציאת הכפולה המשותפת הקטנה ביותר של שני מספרים?

lcm(a, b) = a × b / gcd(a, b), מחושב כך: a / gcd(a, b) × b, כדי שאף ערך ביניים לא יעלה על התוצאה. עבור 4 ו־6, ה־gcd הוא 2, ו־4 / 2 × 6 = 12.

מהי סיבוכיות הזמן של חישוב ה־LCM?

בעזרת נוסחת ה־gcd, זמן הריצה הוא 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

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

סופרים מהמספר הגדול יותר

עבור בקפיצות של כפולות המספר הגדול יותר

חלקו ב־gcd, ואז הכפילו

מלכודות ומקרי קצה

שאלות נפוצות3

בעיות דומות