پرش به محتویات

الگوریتم اقلیدسی تعمیم‌یافته

خب، ببین، الگوریتم اقلیدس معمولی فقط میاد بزرگترین مقسوم‌علیه مشترک (ب.م.م) دو تا عدد صحیح $a$ و $b$ رو حساب می‌کنه. اما این نسخه‌ی «تعمیم‌یافته» یا «پیشرفته» یه کار باحال‌تر هم انجام میده: میاد ب.م.م رو بر حسب خود $a$ و $b$ هم بهت میده. یعنی دو تا ضریب $x$ و $y$ پیدا می‌کنه که توی این معادله صدق کنن:

$$a \cdot x + b \cdot y = \gcd(a, b)$$

یه نکته‌ی مهم اینه که طبق اتحاد بزو، همیشه میشه همچین ضریب‌هایی رو پیدا کرد، پس خیالت راحت باشه. مثلاً، $\gcd(55, 80) = 5$ هست، پس می‌تونیم $5$ رو به صورت یه ترکیب خطی از $55$ و $80$ بنویسیم: $55 \cdot 3 + 80 \cdot (-2) = 5$.

اگه دوست داری شکل کلی‌تری از این مسئله رو ببینی، یه نگاهی به مقاله‌ی معادلات سیاله خطی بنداز. اونجا کل داستان بر پایه‌ی همین الگوریتمیه که الان می‌خوایم یاد بگیریم.

الگوریتم

خب، بریم سراغ خود الگوریتم. از این به بعد، برای راحتی کار، ب.م.م $a$ و $b$ رو با $g$ نشون میدیم.

تغییراتی که باید به الگوریتم اصلی بدیم خیلی ساده‌ست. اگه یادت باشه، الگوریتم اقلیدس معمولی وقتی تموم میشه که $b=0$ باشه. تو این حالت، $a$ همون ب.م.م یا $g$ ماست. پیدا کردن ضریب‌ها برای این حالت پایه (base case) مثل آب خوردنه: $g \cdot 1 + 0 \cdot 0 = g$.

حالا با داشتن این ضریب‌های حالت پایه، یعنی $(x, y) = (1, 0)$، می‌تونیم توی فراخوانی‌های بازگشتی برگردیم عقب و ضریب‌های مراحل قبل رو هم حساب کنیم. تنها کاری که باید بکنیم اینه که بفهمیم وقتی از حالت $(a, b)$ به حالت بعدی یعنی $(b, a \bmod b)$ میریم، ضریب‌های $x$ و $y$ چطوری تغییر می‌کنن.

فرض کن ما یه جوری ضریب‌های $(x_1, y_1)$ رو برای مرحله‌ی بعدی، یعنی برای $(b, a \bmod b)$ پیدا کردیم:

$$b \cdot x_1 + (a \bmod b) \cdot y_1 = g$$

و حالا می‌خوایم با استفاده از اونا، ضریب‌های $(x, y)$ رو برای مرحله‌ی فعلی، یعنی برای $(a, b)$، به دست بیاریم:

$$ a \cdot x + b \cdot y = g$$

خب، بیا اول $a \bmod b$ رو بازنویسی کنیم:

$$ a \bmod b = a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b$$

حالا این عبارت رو توی معادله‌ی اولمون (همونی که برای $x_1$ و $y_1$ بود) جایگزین می‌کنیم:

$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a - \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1$$

و اگه یه کم مرتبش کنیم و بر حسب $a$ و $b$ فاکتور بگیریم، به این می‌رسیم:

$$g = a \cdot y_1 + b \cdot \left( x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)$$

عالی شد! حالا اگه این معادله رو با معادله‌ی اصلیمون یعنی $a \cdot x + b \cdot y = g$ مقایسه کنیم، $x$ و $y$ به راحتی پیدا میشن:

$$\begin{cases} x = y_1 \\ y = x_1 - y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \end{cases} $$

پیاده‌سازی

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

این تابع بازگشتی، هم ب.م.م رو برمی‌گردونه و هم ضریب‌ها رو توی متغیرهای x و y (که به صورت رفرنس بهش دادیم) می‌ریزه.

یه نکته‌ی خوب اینه که این پیاده‌سازی برای عددهای منفی هم درست کار می‌کنه.

نسخه تکراری (Iterative)

میشه الگوریتم اقلیدسی تعمیم‌یافته رو به صورت تکراری هم نوشت. چون دیگه خبری از سربار فراخوانی‌های بازگشتی نیست، این نسخه معمولاً یه کم سریع‌تره.

int gcd(int a, int b, int& x, int& y) {
    x = 1, y = 0;
    int x1 = 0, y1 = 1, a1 = a, b1 = b;
    while (b1) {
        int q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}

اگه به متغیرهای a1 و b1 دقت کنی، می‌بینی که دقیقاً همون مقادیری رو می‌گیرن که توی نسخه‌ی تکراری الگوریتم اقلیدس معمولی داشتیم. پس خیالمون راحته که حداقل ب.م.م رو درست حساب می‌کنه.

حالا برای اینکه بفهمیم چرا ضریب‌ها هم درست در میان، باید از یه چیزی به اسم «نامتغیر» (invariant) کمک بگیریم. نامتغیرها یه سری عبارت هستن که مقدارشون در طول اجرای حلقه ثابت می‌مونه. توی این الگوریتم، این دو تا عبارت همیشه (هم قبل از شروع حلقه و هم بعد از هر بار تکرار) برقرارن:

$$x \cdot a + y \cdot b = a_1$$
$$x_1 \cdot a + y_1 \cdot b = b_1$$

فرض کن مقادیر متغیرها رو بعد از یک بار اجرای حلقه با یه پرایم ($'$) نشون بدیم و $q$ هم همون خارج قسمت $a_1$ بر $b_1$ باشه. از خود الگوریتم اقلیدس می‌دونیم که:

$$a_1' = b_1$$
$$b_1' = a_1 - q \cdot b_1$$

خب، برای اینکه نامتغیر اولمون بعد از آپدیت شدن متغیرها هم برقرار بمونه، باید این رابطه درست باشه:

$$x' \cdot a + y' \cdot b = a_1' = b_1$$

با توجه به نامتغیر دوم (قبل از آپدیت)، می‌دونیم که $b_1 = x_1 \cdot a + y_1 \cdot b$. پس:

$$x' \cdot a + y' \cdot b = x_1 \cdot a + y_1 \cdot b$$

به طور مشابه، برای نامتغیر دوم هم باید این رابطه برقرار باشه:

$$x_1' \cdot a + y_1' \cdot b = b_1' = a_1 - q \cdot b_1$$

با جایگزین کردن مقدار $a_1$ و $b_1$ از نامتغیرهای اصلی، به این می‌رسیم:

$$x_1' \cdot a + y_1' \cdot b = (x \cdot a + y \cdot b) - q \cdot (x_1 \cdot a + y_1 \cdot b)$$
$$x_1' \cdot a + y_1' \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$$

اگه ضریب‌های $a$ و $b$ رو دو طرف تساوی‌ها مقایسه کنی، دقیقاً به همون فرمول‌های آپدیتی می‌رسی که توی کد داریم. این یعنی نامتغیرهای ما در طول اجرای الگوریتم حفظ میشن.

در نهایت، وقتی حلقه تموم میشه، می‌دونیم که $a_1$ همون ب.م.م ماست ($g$). با توجه به نامتغیر اول، داریم: $x \cdot a + y \cdot b = a_1 = g$. این یعنی دقیقاً همون ضریب‌هایی که دنبالشون بودیم رو پیدا کردیم!

حتی می‌تونی کد رو یه کم بهینه‌تر کنی و متغیرهای کمکی a1 و b1 رو حذف کنی و از خود a و b استفاده کنی. ولی اگه این کار رو بکنی، دیگه نمی‌تونی به این راحتی با نامتغیرها درستی الگوریتم رو ثابت کنی.

چند تا مسئله برای تمرین