Least Common Multiple
מקבלים שני מספרים שלמים חיוביים a ו-b. החזירו את הכפולה המשותפת הקטנה ביותר שלהם: המספר השלם החיובי הקטן ביותר שגם a וגם b מחלקים ללא שארית.
לדוגמה, הכפולות של 6 הן 6, 12, 18, 24 וכן הלאה, הכפולות של 8 הן 8, 16, 24 וכן הלאה, והמספר הראשון שמופיע בשתי הרשימות הוא 24.
פונקציה
- ainteger
- המספר השלם החיובי הראשון
- binteger
- המספר השלם החיובי השני
- מחזירהinteger
- המספר השלם החיובי הקטן ביותר שהוא כפולה של a ושל b
אילוצים
1 ≤ a ≤ 1061 ≤ b ≤ 106- התשובה מתאימה למספר שלם חתום בן 32 סיביות:
lcm(a, b) ≤ 231-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 בדיקות נסתרות בשליחה
שאלת המשך
האם תוכל למצוא את המחלק המשותף הגדול ביותר בלי להשתמש כלל בחילוק או בשארית, אלא רק בחיסור ובחלוקה בחצי?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התשובה היא כפולה של המספר הגדול יותר. האם צריך לנסות כל מספר שביניהם, או רק את הכפולות של המספר הגדול יותר?
המחלק המשותף הגדול ביותר והכפולה המשותפת הקטנה ביותר קשורים זה לזה:
gcd(a, b) × lcm(a, b) = a × b. האלגוריתם של אוקלידס מוצא את המחלק המשותף הגדול ביותר בתוך כמה עשרות צעדים.חשב את ה־gcd, ואז החזר
a / gcd × b. חלק קודם: המכפלהa × bעלולה לחרוג ממספר שלם בן 32 סיביות גם כשהתוצאה מתאימה.
פתרון
הכפולה המשותפת הקטנה ביותר והמחלק המשותף הגדול ביותר הם שני צדדים של עובדה אחת: 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חלקו בגורם המשותף הגדול ביותר, ואז הכפילו
האינטואיציה
נפרק את שני המספרים לגורמים ראשוניים. ה־gcd לוקח כל גורם ראשוני בחזקה הקטנה מבין שתי החזקות שלו, וה־lcm לוקח את החזקה הגדולה יותר, וביחד הם משתמשים בכל גורם של a ושל b בדיוק פעם אחת. מכאן נובע ש־gcd(a, b) × lcm(a, b) = a × b, ולכן lcm(a, b) = a × b / gcd(a, b). עבור 4 = 2² ו־6 = 2 × 3, ה־gcd הוא 2 וה־lcm הוא 2² × 3 = 12.
מצאו את ה־gcd באמצעות האלגוריתם של אוקלידס: החליפו את (x, y) ב־(y, x % y) עד ש־y יהיה 0. נדרשות לכך 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 סיביות, והתשובה יוצאת שגויה או שלילית (במקום זאת, גרסת ניפוי שגיאות של Rust קורסת), אף על פי שה-lcm האמיתי נכנס בטווח. - חלוקת
a × bב-gcd באמצעות חשבון בנקודה צפה. התוצאה עלולה להיות2.146654199E9או לאבד את הספרות האחרונות שלה; חשוב לבצע את כל החישובים במספרים שלמים. - הרצת לולאת אוקלידס על
aועלbעצמם, ואז שימוש בהם בנוסחה. אחרי הלולאה הם מכילים את ה-gcd ואת0, ולכן יש לעבוד עם עותקים. - הנחה שהתשובה היא
a × b. זה נכון רק כאשר לשני המספרים אין גורם משותף:lcm(4, 6)הוא12, ולא24.
שאלות נפוצות4
מהי הנוסחה לכפולה המשותפת הקטנה ביותר של שני מספרים?
lcm(a, b) = a × b / gcd(a, b), מחושב כך: a / gcd(a, b) × b, כדי שהערך הביניים לעולם לא יעלה על התוצאה. עבור 4 ו־6, ה־gcd הוא 2, ו־4 / 2 × 6 = 12.
למה gcd(a, b) × lcm(a, b) שווה ל־a × b?
עבור כל מספר ראשוני, ה־gcd משתמש בחזקה הקטנה יותר שלו ב־a וב־b, וה־lcm משתמש בחזקה הגדולה יותר. הקטנה ועוד הגדולה שוות לסכום שתי החזקות, שהוא בדיוק החזקה של אותו מספר ראשוני ב־a × b. כל המספרים הראשוניים תואמים, ולכן שתי המכפלות שוות.
מהי סיבוכיות הזמן של חישוב ה־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 סיביות כשהרשימה ארוכה.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def lcm(a, b):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
a = 4 b = 6
צפוי
12