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

معادله سیاله خطی

یک معادله سیاله خطی (در دو متغیر) معادله‌ای به شکل کلی زیر است:

$$ax + by = c$$

که در آن $a$، $b$ و $c$ اعداد صحیح داده شده و $x$ و $y$ اعداد صحیح مجهول هستند.

در این مقاله، ما چندین مسئله کلاسیک در مورد این معادلات را بررسی می‌کنیم:

  • پیدا کردن یک جواب
  • پیدا کردن تمام جواب‌ها
  • پیدا کردن تعداد جواب‌ها و خود جواب‌ها در یک بازه مشخص
  • پیدا کردن جوابی با کمترین مقدار $x + y$

حالت خاص

یک حالت خاص که باید به آن توجه شود، زمانی است که $a = b = 0$. به راحتی می‌توان دید که بسته به اینکه $c = 0$ باشد یا نه، یا جوابی نداریم یا بی‌نهایت جواب داریم. در ادامه این مقاله، ما این حالت را نادیده می‌گیریم.

راه حل تحلیلی

وقتی $a \neq 0$ و $b \neq 0$، معادله $ax+by=c$ می‌تواند به طور معادل با هر یک از موارد زیر در نظر گرفته شود:

$$\begin{align} ax &\equiv c \pmod b \\ by &\equiv c \pmod a \end{align}$$

بدون از دست دادن کلیت مسئله، فرض کنید که $b \neq 0$ و معادله اول را در نظر بگیرید. وقتی $a$ و $b$ نسبت به هم اول باشند، جواب آن به صورت زیر داده می‌شود:

$$x \equiv ca^{-1} \pmod b,$$

که در آن $a^{-1}$ وارون پیمانه‌ای $a$ به پیمانه $b$ است.

وقتی $a$ و $b$ نسبت به هم اول نباشند، مقادیر $ax$ به پیمانه $b$ برای تمام اعداد صحیح $x$ بر $g=\gcd(a, b)$ بخش‌پذیر هستند، بنابراین جواب تنها زمانی وجود دارد که $c$ بر $g$ بخش‌پذیر باشد. در این حالت، یکی از جواب‌ها را می‌توان با تقسیم کردن معادله بر $g$ پیدا کرد:

$$(a/g) x \equiv (c/g) \pmod{b/g}.$$

بنا به تعریف $g$، اعداد $a/g$ و $b/g$ نسبت به هم اول هستند، بنابراین جواب به صراحت به صورت زیر داده می‌شود:

$$\begin{cases} x \equiv (c/g)(a/g)^{-1}\pmod{b/g},\\ y = \frac{c-ax}{b}. \end{cases}$$

راه حل الگوریتمی

اتحاد بزو (که لم بزو نیز نامیده می‌شود) نتیجه مفیدی است که می‌تواند برای درک راه حل زیر استفاده شود.

فرض کنید $g = \gcd(a,b)$ باشد. آنگاه اعداد صحیح $x,y$ وجود دارند به طوری که $ax + by = g$.

علاوه بر این، $g$ کوچکترین عدد صحیح مثبتی است که می‌توان آن را به صورت $ax + by$ نوشت؛ تمام اعداد صحیح به شکل $ax + by$ مضربی از $g$ هستند.

برای پیدا کردن یک جواب از معادله سیاله با ۲ مجهول، می‌توانید از الگوریتم اقلیدسی تعمیم‌یافته استفاده کنید. ابتدا، فرض کنید که $a$ و $b$ غیرمنفی هستند. وقتی الگوریتم اقلیدسی تعمیم‌یافته را برای $a$ و $b$ به کار می‌بریم، می‌توانیم بزرگترین مقسوم‌علیه مشترک آنها $g$ و ۲ عدد $x_g$ و $y_g$ را پیدا کنیم به طوری که:

$$a x_g + b y_g = g$$

اگر $c$ بر $g = \gcd(a, b)$ بخش‌پذیر باشد، آنگاه معادله سیاله داده شده جواب دارد، در غیر این صورت هیچ جوابی ندارد. اثبات آن ساده است: ترکیب خطی دو عدد بر مقسوم‌علیه مشترک آنها بخش‌پذیر است.

حال فرض کنید که $c$ بر $g$ بخش‌پذیر است، آنگاه داریم:

$$a \cdot x_g \cdot \frac{c}{g} + b \cdot y_g \cdot \frac{c}{g} = c$$

بنابراین یکی از جواب‌های معادله سیاله عبارت است از:

$$x_0 = x_g \cdot \frac{c}{g},$$
$$y_0 = y_g \cdot \frac{c}{g}.$$

ایده بالا همچنان زمانی که $a$ یا $b$ یا هر دو منفی باشند، کار می‌کند. فقط لازم است در صورت لزوم علامت $x_0$ و $y_0$ را تغییر دهیم.

در نهایت، می‌توانیم این ایده را به صورت زیر پیاده‌سازی کنیم (توجه داشته باشید که این کد حالت $a = b = 0$ را در نظر نمی‌گیرد):

```cpp file=linear_diophantine_any 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; }

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) { g = gcd(abs(a), abs(b), x0, y0); if (c % g) { return false; }

x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;

} ```

به دست آوردن تمام جواب‌ها

از یک جواب $(x_0, y_0)$، می‌توانیم تمام جواب‌های معادله داده شده را به دست آوریم. فرض کنید $g = \gcd(a, b)$ و $x_0, y_0$ اعداد صحیحی باشند که در رابطه زیر صدق می‌کنند: $$a \cdot x_0 + b \cdot y_0 = c$$ حال، باید ببینیم که اضافه کردن $b / g$ به $x_0$ و همزمان کم کردن $a / g$ از $y_0$ تساوی را بر هم نمی‌زند: $$a \cdot \left(x_0 + \frac{b}{g}\right) + b \cdot \left(y_0 - \frac{a}{g}\right) = a \cdot x_0 + b \cdot y_0 + a \cdot \frac{b}{g} - b \cdot \frac{a}{g} = c$$ بدیهی است که این فرآیند را می‌توان دوباره تکرار کرد، بنابراین تمام اعداد به شکل زیر: $$x = x_0 + k \cdot \frac{b}{g}$$ $$y = y_0 - k \cdot \frac{a}{g}$$ جواب‌های معادله سیاله داده شده هستند. از آنجایی که معادله خطی است، تمام جواب‌ها روی یک خط قرار دارند، و بنا به تعریف $g$، این مجموعه تمام جواب‌های ممکن معادله سیاله داده شده است.

پیدا کردن تعداد جواب‌ها و خود جواب‌ها در یک بازه مشخص

از بخش قبل، باید مشخص شده باشد که اگر هیچ محدودیتی بر جواب‌ها اعمال نکنیم، تعداد بی‌نهایتی از آنها وجود خواهد داشت. بنابراین در این بخش، ما محدودیت‌هایی را روی بازه $x$ و $y$ اضافه می‌کنیم و سعی خواهیم کرد تمام جواب‌ها را بشماریم و لیست کنیم. فرض کنید دو بازه $[min_x; max_x]$ و $[min_y; max_y]$ وجود داشته باشد و بگوییم که ما فقط می‌خواهیم جواب‌ها را در این دو بازه پیدا کنیم. توجه داشته باشید که اگر $a$ یا $b$ برابر $0$ باشد، آنگاه مسئله فقط یک جواب دارد. ما این حالت را در اینجا در نظر نمی‌گیریم. ابتدا، می‌توانیم جوابی را پیدا کنیم که کمترین مقدار $x$ را داشته باشد، به طوری که $x \ge min_x$. برای انجام این کار، ابتدا هر جوابی از معادله سیاله را پیدا می‌کنیم. سپس، این جواب را طوری جابجا (shift) می‌کنیم که $x \ge min_x$ برقرار شود (با استفاده از آنچه در بخش قبل در مورد مجموعه تمام جواب‌ها آموختیم). این کار را می‌توان در $O(1)$ انجام داد. این حداقل مقدار $x$ را با $l_{x1}$ نشان می‌دهیم. به طور مشابه، می‌توانیم حداکثر مقدار $x$ را که در $x \le max_x$ صدق می‌کند، پیدا کنیم. این حداکثر مقدار $x$ را با $r_{x1}$ نشان می‌دهیم. به طور مشابه، می‌توانیم حداقل مقدار $y$ $(y \ge min_y)$ و حداکثر مقدار $y$ $(y \le max_y)$ را پیدا کنیم. مقادیر متناظر $x$ را با $l_{x2}$ و $r_{x2}$ نشان می‌دهیم. جواب نهایی، تمام جواب‌هایی است که x آنها در اشتراک $[l_{x1}, r_{x1}]$ و $[l_{x2}, r_{x2}]$ قرار دارد. این اشتراک را با $[l_x, r_x]$ نشان می‌دهیم. کد زیر این ایده را پیاده‌سازی می‌کند. توجه داشته باشید که ما در ابتدا $a$ و $b$ را بر $g$ تقسیم می‌کنیم. از آنجایی که معادله $a x + b y = c$ معادل معادله $\frac{a}{g} x + \frac{b}{g} y = \frac{c}{g}$ است، می‌توانیم به جای آن از این معادله استفاده کنیم و در نتیجه $\gcd(\frac{a}{g}, \frac{b}{g}) = 1$ خواهیم داشت، که فرمول‌ها را ساده‌تر می‌کند. cpp file=linear_diophantine_all void shift_solution(int & x, int & y, int a, int b, int cnt) { x += cnt * b; y -= cnt * a; } int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) { int x, y, g; if (!find_any_solution(a, b, c, x, y, g)) return 0; a /= g; b /= g; int sign_a = a > 0 ? +1 : -1; int sign_b = b > 0 ? +1 : -1; shift_solution(x, y, a, b, (minx - x) / b); if (x < minx) shift_solution(x, y, a, b, sign_b); if (x > maxx) return 0; int lx1 = x; shift_solution(x, y, a, b, (maxx - x) / b); if (x > maxx) shift_solution(x, y, a, b, -sign_b); int rx1 = x; shift_solution(x, y, a, b, -(miny - y) / a); if (y < miny) shift_solution(x, y, a, b, -sign_a); if (y > maxy) return 0; int lx2 = x; shift_solution(x, y, a, b, -(maxy - y) / a); if (y > maxy) shift_solution(x, y, a, b, sign_a); int rx2 = x; if (lx2 > rx2) swap(lx2, rx2); int lx = max(lx1, lx2); int rx = min(rx1, rx2); if (lx > rx) return 0; return (rx - lx) / abs(b) + 1; }

هنگامی که $l_x$ و $r_x$ را داریم، لیست کردن تمام جواب‌ها نیز ساده است. کافیست از $x = l_x$ شروع کرده و با گام‌های به اندازه $\text{abs}(b/g)$ تا $x \le r_x$ پیش برویم و برای هر $x$ مقدار متناظر $y$ را با استفاده از معادله $ax+by=c$ محاسبه کنیم.

پیدا کردن جوابی با کمترین مقدار $x + y$

در اینجا نیز باید برای $x$ و $y$ محدودیت‌هایی قائل شد، در غیر این صورت، جواب ممکن است منفی بی‌نهایت شود.

ایده مشابه بخش قبل است: یک جواب دلخواه از معادله سیاله را پیدا می‌کنیم و سپس جواب را برای برآورده کردن برخی شرایط، جابجا (shift) می‌کنیم.

در نهایت، با استفاده از دانشی که از مجموعه تمام جواب‌ها داریم، کمترین مقدار را پیدا می‌کنیم:

$$x' = x + k \cdot \frac{b}{g},$$
$$y' = y - k \cdot \frac{a}{g}.$$

توجه داشته باشید که $x + y$ به صورت زیر تغییر می‌کند:

$$x' + y' = x + y + k \cdot \left(\frac{b}{g} - \frac{a}{g}\right) = x + y + k \cdot \frac{b-a}{g}$$

اگر $a < b$ باشد، باید کوچکترین مقدار ممکن $k$ را انتخاب کنیم. اگر $a > b$ باشد، باید بزرگترین مقدار ممکن $k$ را انتخاب کنیم. اگر $a = b$ باشد، تمام جواب‌ها مجموع $x + y$ یکسانی خواهند داشت.

مسائل تمرینی