Problem link ও উৎস
- **Original source:** CP-Algorithms — Extended Euclidean Algorithm
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** back substitution
- **Basic idea inherited from:** 018, 019 (gcd / Euclid algorithm)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো integer `a` আর `b` দেওয়া আছে। শুধু তাদের `gcd(a, b)` বের করলেই হবে না — সেই সাথে দুটো integer `x` আর `y`-ও খুঁজে দিতে হবে, যাতে এই সম্পর্কটা মেলে:
```
a · x + b · y = gcd(a, b)
```
মানে gcd-টাকে a আর b-এর একটা "ওজন-মেশানো যোগফল" (integer combination) হিসেবে লিখতে হবে। সাধারণ Euclid শুধু gcd দেয়; extended Euclid সেই gcd বানানোর recipe-টাও (x, y) দেয়।
ছোট করে বলি: এটা Level 10-এর একদম প্রথম problem, আর পুরো level-এর ভিত্তি। কারণ এই x-টাই পরে modular inverse (130), CRT (127), আর Diophantine (126)-এর মূল চাবি হয়ে দাঁড়াবে। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু এই একটা problem না বুঝলে পরের তিনটা ঝুলে যাবে।
### Input ও output {#6-example-input-and-output}
```text
input (a, b) -> output (g, x, y) যাচাই (a·x + b·y)
-----------------------------------------------------------------
30, 18 -> (6, -1, 2) 30·(-1) + 18·2 = 6 ✓
35, 15 -> (5, 1, -2) 35·1 + 15·(-2) = 5 ✓
17, 5 -> (1, -2, 7) 17·(-2) + 5·7 = 1 ✓ (coprime)
12, 0 -> (12, 1, 0) 12·1 + 0·0 = 12 ✓ (b = 0)
0, 7 -> (7, 0, 1) 0·0 + 7·1 = 7 ✓ (a = 0)
48, 36 -> (12, 1, -1) 48·1 + 36·(-1) = 12 ✓
```
দুটো edge case খেয়াল করো: **b = 0** হলে gcd = a, আর x = 1, y = 0 (কারণ `a·1 + 0·0 = a`)। আর **coprime** (gcd = 1) হলে x ঠিক a-এর inverse mod b হয়ে দাঁড়ায় — সেটাই 130-তে কাজে লাগবে। (x, y-এর মান unique নয়; একই gcd-এর জন্য একাধিক (x, y) সম্ভব, আমরা একটা valid জোড়া দিই।)
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে দুই ধরনের weight আছে — একটা `a` গ্রামের, একটা `b` গ্রামের। একটা দাঁড়িপাল্লায় তুমি এই weight গুলো দুই পাশে রেখে চাও একদম ছোট সম্ভব পার্থক্য (যেটা হলো gcd) মাপতে।
- `x` মানে: a-গ্রামের weight কয়টা, আর কোন পাশে (positive হলে এক পাশ, negative হলে উল্টো পাশ)
- `y` মানে: b-গ্রামের weight কয়টা, কোন পাশে
extended Euclid তোমাকে শুধু বলে না "সবচেয়ে ছোট মাপ কত" — সে তোমাকে **ঠিক recipe** দেয়: কয়টা a-weight, কয়টা b-weight, কোন পাশে রাখলে ওই ছোট মাপটা পাবে। সাধারণ Euclid শুধু মাপটা বলত; extended বলে কীভাবে সাজাবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **018, 019 (gcd / Euclid)**-এর extension। সাধারণ Euclid মনে করো:
```
gcd(a, b) = gcd(b, a % b), আর gcd(a, 0) = a
```
extended Euclid ঠিক একই recursion-এর সিঁড়ি বেয়ে নামে — শুধু পার্থক্য, ফেরার সময় সে gcd-এর সাথে x, y-ও বয়ে আনে। তাই Euclid যদি বন্ধু হয়, extended Euclid হলো সেই বন্ধু যে শুধু গন্তব্যে পৌঁছায় না, ফেরার সময় পুরো রাস্তার ম্যাপটাও এঁকে আনে।
এর উপরে আবার দাঁড়াবে: **126 (Diophantine)** — এক solution পেতে, **127 (CRT)** — modulus merge করতে, **130 (modular inverse)** — inverse বের করতে। তাই এটা পুরো level-এর শিকড়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea-টা একটা গভীর theorem থেকে আসে — **Bézout's identity**: যেকোনো দুটো integer a, b-এর জন্য এমন integer x, y থাকবেই যাতে `a·x + b·y = gcd(a, b)`। আর শুধু থাকবে না — Euclid-এর সিঁড়ি বেয়ে নেমে আবার উঠে এসে আমরা সেটা **হাতে বানিয়ে** ফেলতে পারি।
এই level CP-leaning হলেও idea-টা চমৎকার সরল: Euclid যখন `gcd(a, b)` বের করে, প্রতি ধাপে সে লেখে `a = q·b + r` (q = ভাগফল, r = ভাগশেষ)। আমরা যদি প্রতিটা ধাপের ভাগশেষকে মনে রাখি, তাহলে শেষে নিচে নেমে gcd পাওয়ার পর সেই ভাগশেষগুলোকে উল্টোপথে substitute করতে করতে উপরে উঠে gcd-কে a আর b-এর ভাষায় লিখে ফেলা যায়। এটাই **back substitution**।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
x, y না জেনে শুরু করলে প্রথম যে naive idea আসে — **সব ছোট integer জোড়া ধরে চেষ্টা করা**। আগে সাধারণ Euclid দিয়ে g = gcd বের করি, তারপর x আর y-কে একটা range-এ ঘুরিয়ে দেখি কোন জোড়ায় `a·x + b·y == g` মেলে:
```python
def ext_gcd_brute(a, b):
from math import gcd
g = gcd(a, b)
limit = max(abs(a), abs(b)) + 1 # |x|, |y| এর মোটামুটি সীমা
for x in range(-limit, limit + 1):
for y in range(-limit, limit + 1):
if a * x + b * y == g:
return g, x, y
return g, None, None
```
ছোট সংখ্যায় (যেমন 30, 18) এটা ঠিক জোড়া (একটা valid x, y) খুঁজে দেয়। বড়জোর "কোনোভাবে হলেও হলো" — কিন্তু এটাই আমাদের শুরু।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা স্পষ্ট — এটা **দুটো nested loop**, প্রতিটা প্রায় `max(a, b)` লম্বা। তাই মোট কাজ O(a · b)-এর কাছাকাছি, মানে দুটো সংখ্যার গুণফলের মাপের।
```text
a, b ছোট (30, 18): ~60 × 60 = 3,600 জোড়া পরীক্ষা — চোখের পলকে
a, b মাঝারি (10⁶): ~10⁶ × 10⁶ = 10¹² জোড়া — কয়েক ঘণ্টা/দিন!
```
মানে সংখ্যা একটু বড় হলেই brute force কার্যত অচল। অথচ সাধারণ Euclid নিজেই O(log min(a, b))-এ gcd বের করে — তাহলে x, y বের করতেও তো log ধাপেই হওয়া উচিত, পুরো grid চষার দরকার নেই। সেটাই extended Euclid-এর প্রতিশ্রুতি।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **back-substitution-টা recursion নিজেই করে দিতে পারে।** আলাদা করে সব ভাগশেষ খাতায় লিখে উপরে ওঠার দরকার নেই — recursion যখন নিচ থেকে ফেরে, প্রতিটা return-এ x, y update করে নিয়ে এলেই হলো।
ধরো আমরা `b` আর `a % b`-এর জন্য ইতিমধ্যে (x₁, y₁) পেয়েছি:
```text
b·x₁ + (a % b)·y₁ = g
```
এখন `a % b = a − (a // b)·b` বসিয়ে দিই:
```text
b·x₁ + (a − (a // b)·b)·y₁ = g
a·y₁ + b·(x₁ − (a // b)·y₁) = g
```
মিলিয়ে দেখো — a-এর সহগ এখন `y₁`, আর b-এর সহগ `x₁ − (a // b)·y₁`। মানে:
```text
নতুন x = y₁
নতুন y = x₁ − (a // b)·y₁
```
এই দুই লাইনের update rule-ই পুরো algorithm। recursion শেষ হয় `b = 0`-তে, যেখানে `a·1 + 0·0 = a` — তাই base case `(a, 1, 0)`।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **g বানানোর recipe-টা return-এর সময় বয়ে আনা যায় — gcd আর তার combination একই recursion-এ একসাথে উঠে আসে।**
brute force পুরো (x, y) grid খুঁজছিল; tweak হলো — Euclid যে সিঁড়ি বেয়ে এমনিতেই নামছে, ঠিক সেই সিঁড়ি বেয়ে ফেরার সময় দুটো extra সংখ্যা (x, y) update করে নিয়ে এসো। O(a·b) থেকে সোজা O(log min(a, b))-এ নেমে এল, কারণ Euclid নিজেই log ধাপে নামে।
(সতর্কতা: এই `x = y₁, y = x₁ − (a//b)·y₁` rule-টা একবার নিজে খাতায় gcd(30, 18)-এ verify না করলে মুখস্থ ভুল হবেই — এটাই এই level-এর #১ common mistake।)
### ছবিতে বোঝা {#5-visual-explanation}
`gcd(30, 18)`-এর পুরো যাত্রা দেখি — আগে সিঁড়ি বেয়ে নামা (Euclid), তারপর back-substitution-এ উঠে আসা:
```text
নামা (Euclid division steps):
30 = 1·18 + 12
18 = 1·12 + 6
12 = 2· 6 + 0 <- ভাগশেষ 0, তাই gcd = 6
ওঠা (back-substitution, ভাগশেষকে আগের লাইনে বদলাই):
6 = 18 − 1·12 [দ্বিতীয় লাইন থেকে 6 আলাদা করলাম]
= 18 − 1·(30 − 1·18) [12 = 30 − 1·18 বসালাম]
= 18 − 1·30 + 1·18
= 2·18 − 1·30
⇒ 30·(−1) + 18·(2) = 6 ✓
ফল: x = −1, y = 2
যাচাই: 30·(−1) + 18·2 = −30 + 36 = 6 = gcd ✓
```
লক্ষ করো — নিচে নামার সময় প্রতিটা ভাগশেষ (12, তারপর 6) তৈরি হলো; উপরে ওঠার সময় সেই ভাগশেষগুলোকে একে একে আগের সংখ্যার ভাষায় লিখে শেষে শুধু 30 আর 18 রয়ে গেল। এটাই সিঁড়ির খেলা।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`ext_gcd(30, 18)` recursion-এর সিঁড়ি — আগে নিচে নামা (call), তারপর ফেরা (return) সহ:
| call | a | b | a % b | a // b | কী হবে |
| --- | --- | --- | --- | --- | --- |
| 1 | 30 | 18 | 12 | 1 | ext_gcd(18, 12)-এর জন্য অপেক্ষা |
| 2 | 18 | 12 | 6 | 1 | ext_gcd(12, 6)-এর জন্য অপেক্ষা |
| 3 | 12 | 6 | 0 | 2 | ext_gcd(6, 0)-এর জন্য অপেক্ষা |
| 4 | 6 | 0 | — | — | base case → return (6, 1, 0) |
এবার ফেরার পথ (নিচ থেকে উপরে), update rule `x = y₁, y = x₁ − (a//b)·y₁`:
| ফেরা | পেলাম (g, x₁, y₁) | a // b | নতুন x = y₁ | নতুন y = x₁ − (a//b)·y₁ | return |
| --- | --- | --- | --- | --- | --- |
| call 4 → 3 | (6, 1, 0) | 2 | 0 | 1 − 2·0 = 1 | (6, 0, 1) |
| call 3 → 2 | (6, 0, 1) | 1 | 1 | 0 − 1·1 = −1 | (6, 1, −1) |
| call 2 → 1 | (6, 1, −1) | 1 | −1 | 1 − 1·(−1) = 2 | (6, −1, 2) |
শেষ return: `(6, −1, 2)`। যাচাই: `30·(−1) + 18·2 = −30 + 36 = 6` ✓। দেখো — back-substitution-এর সেই সিঁড়িটাই recursion নিজে নিজে চড়ে উঠল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def ext_gcd(a, b):
"""gcd(a, b) এবং এমন (x, y) ফেরত দেয় যাতে a*x + b*y = gcd(a, b)।"""
if b == 0:
return a, 1, 0 # a*1 + 0*0 = a
g, x1, y1 = ext_gcd(b, a % b) # b*x1 + (a % b)*y1 = g
x = y1
y = x1 - (a // b) * y1
return g, x, y
def ext_gcd_iter(a, b):
"""একই কাজ, কিন্তু loop দিয়ে (recursion-এর গভীরতা এড়াতে)।"""
old_r, r = a, b
old_x, x = 1, 0
old_y, y = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y # (g, x, y)
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def check(a, b):
"""দুই version মেলে কিনা, আর a*x + b*y == g কিনা যাচাই করে।"""
g1, x1, y1 = ext_gcd(a, b)
g2, x2, y2 = ext_gcd_iter(a, b)
assert g1 == gcd(a, b), f"gcd ভুল: {a},{b}"
assert a * x1 + b * y1 == g1, f"recursive identity ভুল: {a},{b}"
assert a * x2 + b * y2 == g2, f"iterative identity ভুল: {a},{b}"
assert g1 == g2, f"দুই version-এর gcd আলাদা: {a},{b}"
check(30, 18)
check(35, 15)
check(17, 5)
check(12, 0)
check(0, 7)
check(48, 36)
check(99, 78)
check(1, 1)
check(1000000007, 998244353) # বড় coprime জোড়া
g, x, y = ext_gcd(30, 18)
assert (g, x, y) == (6, -1, 2)
print(ext_gcd(30, 18)) # (6, -1, 2)
print(ext_gcd(35, 15)) # (5, 1, -2)
print(ext_gcd_iter(17, 5)) # (1, -2, 7)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def ext_gcd(a, b):
if b == 0:
return a, 1, 0
```
base case — `b` শূন্য হলে gcd হলো `a` নিজেই, আর `a·1 + 0·0 = a` মেলে, তাই x = 1, y = 0।
```
g, x1, y1 = ext_gcd(b, a % b)
```
ছোট সমস্যাটা আগে solve করছি — `b` আর `a % b`-এর জন্য (g, x₁, y₁) পাচ্ছি, যেখানে `b·x₁ + (a % b)·y₁ = g`। এটাই Euclid-এর সিঁড়ি নিচে নামা।
```
x = y1
y = x1 - (a // b) * y1
return g, x, y
```
ফেরার সময় section 9-এর algebra প্রয়োগ — নতুন x হলো পুরোনো y₁, আর নতুন y হলো `x₁ − (a // b)·y₁`। gcd একই থাকে, শুধু সহগ দুটো update হয়।
```
def ext_gcd_iter(a, b):
old_r, r = a, b
old_x, x = 1, 0
old_y, y = 0, 1
while r != 0:
q = old_r // r
...
```
iterative রূপ — তিন জোড়া variable (remainder, x, y) একসাথে এগোয়। প্রতি ধাপে ভাগফল `q` বের করে তিনটাকেই একই rule-এ update করি। এতে recursion-এর গভীরতা (deep recursion) এড়ানো যায়, বড় input-এ নিরাপদ।
বাকি `check` function আর `assert` লাইনগুলো নিজেরাই যাচাই করে — দুই version মেলে কিনা, আর মূল identity `a·x + b·y == g` সত্যি কিনা। সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
(6, -1, 2)
(5, 1, -2)
(1, -2, 7)
সব test pass!
```
প্রথম লাইন `ext_gcd(30, 18)` → (6, −1, 2), মানে `30·(−1) + 18·2 = 6`। দ্বিতীয় `ext_gcd(35, 15)` → (5, 1, −2), মানে `35·1 + 15·(−2) = 5`। তৃতীয় `ext_gcd_iter(17, 5)` → (1, −2, 7), মানে `17·(−2) + 5·7 = 1` (coprime, তাই gcd 1)। তার আগের সব `assert` চুপচাপ pass করেছে — তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log min(a, b))** — ঠিক সাধারণ Euclid-এর মতোই। প্রতি ধাপে `(a, b)` থেকে `(b, a % b)`-তে যাই, আর Euclid-এর তত্ত্ব বলে দুই ধাপে সংখ্যা অন্তত অর্ধেক হয় (Fibonacci জোড়া worst case)। তাই ধাপ সংখ্যা ছোট সংখ্যাটার অঙ্ক-সংখ্যার সমানুপাতিক — logarithmic। brute force-এর O(a·b) থেকে আকাশ-পাতাল পার্থক্য।
### অতিরিক্ত জায়গা {#16-space-complexity}
**Recursive version: O(log min(a, b))** — recursion-এর গভীরতা যত ধাপ, তত stack frame। **Iterative version: O(1)** — মাত্র গুটিকয় variable, কোনো extra array নেই। বড় input-এ iterative version-ই নিরাপদ (Python-এ default recursion limit-এ ধাক্কা খাবে না)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Update rule গুলিয়ে ফেলা** — সবচেয়ে কমন ভুল। `x = y₁, y = x₁ − (a//b)·y₁` — কেউ x আর y উল্টে ফেলে, কেউ `(a//b)` ভুলে যায়। একটা ছোট উদাহরণে (gcd(30, 18)) হাতে verify না করে কখনো ছাড়বে না।
2. **base case ভুল** — `b == 0`-তে return `(a, 1, 0)` হওয়া উচিত; কেউ ভুল করে `(a, 0, 1)` বা `(b, ...)` লেখে।
3. **negative x, y-কে ভুল ভাবা** — x বা y negative হওয়া স্বাভাবিক ও সঠিক; minus দেখে ভয় পেয়ো না, identity মিললেই হলো।
4. **x, y unique ভাবা** — একই gcd-এর জন্য অসীম (x, y) জোড়া আছে (`x + k·b/g, y − k·a/g`)। তোমার উত্তর reference-এর সাথে হুবহু না মিললেও যদি `a·x + b·y == g` মেলে, সেটা সঠিক।
5. **বড় input-এ recursion limit** — Python-এ অতি বড় বা বিশেষ জোড়ায় recursion গভীরে গেলে error; তখন iterative version use করো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Exponentiation II** (