রৈখিক ডায়োফ্যান্টাইন সমীকরণ#
একটি রৈখিক ডায়োফ্যান্টাইন সমীকরণ (দুটি চলকে) হলো নিম্নলিখিত সাধারণ আকারের একটি সমীকরণ:
$$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}$ হলো $b$ মডুলোতে $a$-এর মডুলার ইনভার্স।
যখন $a$ ও $b$ সহমৌলিক নয়, তখন সকল পূর্ণসংখ্যা $x$-এর জন্য $ax$ মডুলো $b$-এর মান $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$ কেসটি বিবেচনা করে না):
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$$এখন লক্ষ্য করা উচিত যে $x_0$-এর সাথে $b / g$ যোগ করলে, এবং একই সময়ে $y_0$ থেকে $a / g$ বিয়োগ করলে সমতা ভঙ্গ হবে না:
$$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$। এটি করতে, আমরা প্রথমে ডায়োফ্যান্টাইন সমীকরণের যেকোনো একটি সমাধান বের করি। তারপর, পূর্ববর্তী বিভাগে সকল সমাধানের সেট সম্পর্কে আমরা যা জানি তা ব্যবহার করে এই সমাধানটিকে শিফট করি $x \ge min_x$ পেতে। এটি $O(1)$-তে করা যায়। $x$-এর এই সর্বনিম্ন মানকে $l_{x1}$ বলে চিহ্নিত করি।
একইভাবে, $x \le max_x$ সিদ্ধ করে এমন $x$-এর সর্বোচ্চ মান বের করা যায়। $x$-এর এই সর্বোচ্চ মানকে $r_{x1}$ বলে চিহ্নিত করি।
একইভাবে, $y$-এর সর্বনিম্ন মান $(y \ge min_y)$ এবং সর্বোচ্চ মান $(y \le max_y)$ বের করা যায়। $x$-এর সংশ্লিষ্ট মানগুলোকে $l_{x2}$ ও $r_{x2}$ বলে চিহ্নিত করি।
চূড়ান্ত সমাধান হলো $[l_{x1}, r_{x1}]$ ও $[l_{x2}, r_{x2}]$-এর ছেদে x-সহ সকল সমাধান। এই ছেদকে $[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$ পেতে পারি, যা সূত্রগুলো সরল করে।
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$ পেলে, সকল সমাধান তালিকাভুক্ত করাও সহজ। শুধু সকল $k \ge 0$-এর জন্য $x = l_x + k \cdot \frac{b}{g}$ ইটারেট করতে হবে $x = r_x$ পর্যন্ত, এবং $a x + b y = c$ সমীকরণ ব্যবহার করে সংশ্লিষ্ট $y$ মান বের করতে হবে।
$x + y$-এর সর্বনিম্ন মানসহ সমাধান নির্ণয় { data-toc-label=‘Find the solution with minimum value of ’ }#
এখানে, $x$ ও $y$-তেও কিছু সীমাবদ্ধতা দিতে হবে, অন্যথায়, উত্তর ঋণাত্মক অসীম হতে পারে।
ধারণাটি পূর্ববর্তী বিভাগের মতোই: আমরা ডায়োফ্যান্টাইন সমীকরণের যেকোনো একটি সমাধান বের করি, তারপর সমাধানটিকে শিফট করি কিছু শর্ত পূরণ করতে।
পরিশেষে, সকল সমাধানের সেটের জ্ঞান ব্যবহার করে সর্বনিম্ন খুঁজে বের করি:
$$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$-এর যোগফল একই থাকবে।