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) לכפולה המשותפת הקטנה ביותר (LCM)?

המחלק המשותף הגדול ביותר הוא המספר הגדול ביותר שמחלק את שני הקלטים; הכפולה המשותפת הקטנה ביותר היא המספר הקטן ביותר ששני הקלטים מחלקים. הם קשורים באמצעות 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

צפוי