Problem link ও উৎস
- **Original source:** CP-Algorithms — Extended Euclidean algorithm
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Hard
- **Pattern:** back-substitution — a·x + b·y = gcd(a, b)
- **Basic idea inherited from:** 018 — GCD using Euclidean Algorithm
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো integer `a` আর `b` দেওয়া আছে। শুধু gcd(a, b) বের করলেই হবে না — এমন দুটো integer `x` আর `y`-ও খুঁজে বের করতে হবে যাতে:
```text
a · x + b · y = gcd(a, b)
```
উদাহরণ: a = 48, b = 18 হলে gcd = 6, আর একটা সমাধান হলো x = −1, y = 3, কারণ `48 × (−1) + 18 × 3 = −48 + 54 = 6`। ঠিকঠাক!
মানে শুধু "সবচেয়ে বড় common divisor কত" নয়, "সেই divisor-কে a আর b-র একটা যোগফল হিসেবে কীভাবে সাজানো যায়" — সেই coefficient দুটো বের করাই কাজ।
### Input ও output {#6-example-input-and-output}
```text
a , b -> (g, x, y) যাচাই: a·x + b·y
-----------------------------------------------
48 , 18 -> (6, -1, 3) 48·(-1)+18·3 = 6 ✓
30 , 20 -> (10, 1, -1) 30·1 + 20·(-1) = 10 ✓
35 , 15 -> (5, 1, -2) 35·1 + 15·(-2) = 5 ✓
7 , 0 -> (7, 1, 0) 7·1 + 0·0 = 7 ✓
3 , 5 -> (1, 2, -1) 3·2 + 5·(-1) = 1 ✓ (coprime)
```
খেয়াল করো: x, y **একমাত্র নয়** — একাধিক জোড়া কাজ করে (যেমন 48·(−1)+18·3 = 6, আবার 48·2+18·(−5) = 6-ও হয়)। আমরা যেটা পাই, সেটা একটা বৈধ সমাধান; verify করার সময় সবসময় `a·x + b·y == g` চেক করব, ঠিক কোন জোড়া বেরিয়েছে তা নয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে শুধু দুই মাপের ওজন আছে — 48 গ্রামের আর 18 গ্রামের বাটখারা — আর একটা দুই-পাল্লার দাঁড়িপাল্লা। তুমি জানতে চাও: এই দুটো দিয়ে ঠিক **6 গ্রাম** ওজন মাপা যায় কি না।
হ্যাঁ যায় — এক পাল্লায় একটা 18 আর আরেকটা 18 (মোট 54), অন্য পাল্লায় একটা 48 রাখলে পার্থক্য 54 − 48 = 6। মানে "18 তিনবার যোগ, 48 একবার বিয়োগ" → `18×3 + 48×(−1) = 6`। এখানে ধনাত্মক coefficient মানে "এই পাল্লায়", ঋণাত্মক মানে "ওই পাল্লায়"।
Extended GCD আসলে তোমাকে সেই recipe-টাই বলে দেয়: কোন বাটখারা কতবার, কোন পাল্লায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **018 (GCD using Euclidean Algorithm)**-এর উপর দাঁড়িয়ে। 018-এ আমরা শুধু সংখ্যাটা (gcd) ফেরত দিতাম; এখানে সেই একই ধাপগুলো ধরে রেখে, প্রতিবার coefficient-ও বয়ে নিয়ে যাই।
মূল পার্থক্য: 018 শুধু "কত" বলে; 019 বলে "কীভাবে a আর b মিলিয়ে সেই 'কত' বানানো যায়"। তাই 018 ভালো করে বুঝে না থাকলে আগে সেখানে এক ধাপ পিছিয়ে যাও — back-substitution আসলে সেই ধাপগুলোরই উল্টো যাত্রা।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
পেছনের গণিতটার নাম **Bézout's identity**: যেকোনো দুটো integer a, b-র জন্য এমন x, y থাকবেই যাতে `a·x + b·y = gcd(a, b)`। শুধু থাকে না — Euclid-এর ধাপগুলো উল্টোদিকে হাঁটলে (back-substitution) ওদের আসলেই বের করা যায়।
Core idea: সাধারণ Euclid যখন `(a, b)` থেকে `(b, a % b)`-তে নামে, তখন প্রতিটা remainder আসলে `a` আর `b`-র একটা যোগফল হিসেবে লেখা যায়। সবচেয়ে নিচের ধাপে (যেখানে gcd বেরোয়) সেই যোগফলের coefficient গুলোই আমাদের x, y।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
x, y কত হতে পারে না জানলে, সবচেয়ে সরল চিন্তা — প্রথমে সাধারণ gcd বের করি, তারপর x-কে একটা range-এ ঘুরিয়ে দেখি কোন x-এর জন্য `(g − a·x)` ঠিকঠাক `b` দিয়ে ভাগ যায় (তাহলেই y = (g − a·x) / b পূর্ণসংখ্যা):
```python
def extgcd_brute(a, b):
from math import gcd
g = gcd(a, b)
if b == 0:
return (g, 1, 0)
# x ছোট range-এ খুঁজি: এমন x যাতে (g - a*x) b দিয়ে ভাগ যায়
for x in range(-abs(b), abs(b) + 1):
if (g - a * x) % b == 0:
y = (g - a * x) // b
return (g, x, y)
```
এটা |b| range-এ x খুঁজে একটা বৈধ জোড়া দেয় — কারণ একটা সমাধান সবসময় ওই range-এ থাকে। ঠিক উত্তরই বেরোয়, শুধু সাজানো নয়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই loop সবচেয়ে খারাপ ক্ষেত্রে `2·|b|` বার ঘোরে। b ছোট হলে ঠিক আছে, কিন্তু b যদি 10⁹ হয়, তাহলে প্রায় ২০০ কোটি বার loop — Time Limit Exceeded।
```text
b = 1000000000 হলে:
brute force : ~2×10^9 বার loop (ধীর, O(b))
extended Euclid : ~30 ধাপের কম (O(log min(a, b)), GCD-র মতোই)
```
মূল সমস্যা: আমরা x-কে অন্ধভাবে খুঁজছি, যেখানে Euclid-এর ধাপগুলোই আমাদের x, y **হিসাব করে** দিয়ে দিতে পারে। সেই হিসাবটাই দ্রুত পথ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: **base case-এ coefficient জানা, আর প্রতিটা recursion থেকে ফেরার সময় coefficient update করার একটা সরল সূত্র আছে।**
Base case: `extgcd(a, 0) = (a, 1, 0)` — কারণ `a·1 + 0·0 = a = gcd`। সহজ।
Recursive ধাপ: ধরো আমরা ছোট সমস্যা `extgcd(b, a % b)` থেকে `(g, x1, y1)` পেলাম, মানে `b·x1 + (a % b)·y1 = g`। এখন `a % b = a − (a // b)·b` বসিয়ে সাজালে পাওয়া যায়:
```text
g = a·y1 + b·(x1 − (a // b)·y1)
```
তাই বড় সমস্যার উত্তর: `x = y1`, `y = x1 − (a // b)·y1`। এই দুটো সূত্রই পুরো কাজ — কোনো খোঁজাখুঁজি নেই।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **Euclid নিচে নামার সময় শুধু সংখ্যা না, coefficient-ও বয়ে নিলে — ফেরার পথে তারা নিজেরাই সঠিক x, y-তে গুছিয়ে যায়।**
মূল মোচড়টা ওই এক লাইনে: ছোট সমস্যার `(x1, y1)` থেকে বড় সমস্যার `(x, y)` হয় `x = y1`, `y = x1 − (a // b)·y1`। মানে x আর y যেন একে অপরের ভূমিকা বদলে নেয়, আর y-তে quotient `a // b`-র একটা সংশোধন যোগ হয়। এই সূত্রটা মুখস্থ নয় — বুঝে রাখলেই Level 2-তে কাজে দেবে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে সাধারণ Euclid নিচে নামে, তারপর আমরা coefficient নিয়ে আবার উপরে উঠি:
```text
নিচে নামা (সাধারণ Euclid):
48 = 18·2 + 12 <- remainder 12
18 = 12·1 + 6 <- remainder 6 (এটাই gcd)
12 = 6·2 + 0 <- শেষ
উপরে উঠে coefficient সাজানো (back-substitution):
6 = 18 − 12·1
= 18 − (48 − 18·2)·1 [12 = 48 − 18·2 বসালাম]
= 18·3 − 48·1
=> x(for 48) = −1, y(for 18) = 3
```
মিলিয়ে দেখো:
```text
48 · (−1) + 18 · 3
= −48 + 54
= 6 ✓ (= gcd)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো extgcd(48, 18) চালাই। আগে recursion নিচে নামে (base case পর্যন্ত), তারপর ফেরার পথে coefficient গোছায়:
নিচে নামা:
| call | a | b | a // b |
| --- | --- | --- | --- |
| 1 | 48 | 18 | 2 |
| 2 | 18 | 12 | 1 |
| 3 | 12 | 6 | 2 |
| 4 | 6 | 0 | — (base case) |
ফেরার পথ (`x = y1`, `y = x1 − (a//b)·y1`):
| ফিরছি | base/ছোট থেকে (g, x1, y1) | নতুন (g, x, y) |
| --- | --- | --- |
| call 4 | base: (6, 1, 0) | (6, 1, 0) |
| call 3 (a//b=2) | (6, 1, 0) | (6, 0, 1 − 2·0) = (6, 0, 1) |
| call 2 (a//b=1) | (6, 0, 1) | (6, 1, 0 − 1·1) = (6, 1, −1) |
| call 1 (a//b=2) | (6, 1, −1) | (6, −1, 1 − 2·(−1)) = (6, −1, 3) |
শেষ উত্তর **(6, −1, 3)**। যাচাই: `48·(−1) + 18·3 = −48 + 54 = 6` ✓ — section 5-এর হাতে-করা back-substitution-এর সাথে হুবহু মিলল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def extended_gcd(a, b):
"""(g, x, y) ফেরত দেয় যেখানে g = gcd(a, b) আর a·x + b·y = g।"""
if b == 0:
return (a, 1, 0) # base: a·1 + 0·0 = a
g, x1, y1 = extended_gcd(b, a % b)
x = y1 # coefficient গোছানোর সূত্র
y = x1 - (a // b) * y1
return (g, x, y)
def extended_gcd_iter(a, b):
"""একই কাজ, iterative — recursion ছাড়া, বড় input-এ নিরাপদ।"""
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) # (gcd, x, y)
# --- ছোট test গুলো (সব pass করা উচিত) ---
def check(a, b):
g, x, y = extended_gcd(a, b)
assert a * x + b * y == g # Bézout মিলছে?
from math import gcd
assert g == gcd(a, b) # সঠিক gcd?
gi, xi, yi = extended_gcd_iter(a, b)
assert a * xi + b * yi == gi # iterative-ও মিলছে?
assert gi == g
return g, x, y
assert check(48, 18) == (6, -1, 3)
assert check(30, 20)[0] == 10 # g ঠিক; x, y যেকোনো বৈধ জোড়া
assert check(35, 15)[0] == 5
assert check(7, 0) == (7, 1, 0) # base case
assert check(3, 5)[0] == 1 # coprime
assert check(1071, 462)[0] == 21 # বড় উদাহরণ
print(extended_gcd(48, 18)) # (6, -1, 3)
print(extended_gcd(3, 5)) # (1, 2, -1)
print(extended_gcd(7, 0)) # (7, 1, 0)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if b == 0:
return (a, 1, 0)
```
Base case — recursion থামার জায়গা। `b = 0` হলে gcd = a, আর `a·1 + 0·0 = a` মেলে, তাই x = 1, y = 0।
```text
g, x1, y1 = extended_gcd(b, a % b)
```
ছোট সমস্যাটা আগে solve করি (ঠিক 018-এর Euclid-এর মতো নিচে নামা)। ওটা ফেরত দেয় `(g, x1, y1)` যেখানে `b·x1 + (a % b)·y1 = g`।
```text
x = y1
y = x1 - (a // b) * y1
```
এই দুই লাইনই back-substitution-এর প্রাণ। ছোট সমস্যার coefficient থেকে বড় সমস্যার coefficient হিসাব করি (section 9-এর সূত্র)। নতুন x পুরোনো y1, আর নতুন y-তে quotient `a // b`-র সংশোধন।
iterative version-এ একই কাজ tuple-update দিয়ে: `old_r, x, y` ত্রয়ী একসাথে এগোয়, প্রতি ধাপে quotient `q` দিয়ে update — recursion না থাকায় বিশাল input-এও stack overflow হয় না।
`check` function প্রতিবার `a*x + b*y == g` যাচাই করে — অর্থাৎ ঠিক কোন জোড়া বেরোলো তা না দেখে, Bézout মেলে কি না সেটাই assert করি (কারণ সমাধান একাধিক)।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
(6, -1, 3)
(1, 2, -1)
(7, 1, 0)
সব test pass!
```
প্রথম লাইন: extgcd(48,18) = (6, −1, 3), যা section 11-এর dry run-এর সাথে মেলে। দ্বিতীয়: extgcd(3,5) = (1, 2, −1), যাচাই 3·2 + 5·(−1) = 1। তৃতীয়: base case (7,0) = (7, 1, 0)। সব `assert` (যেগুলো প্রতিবার Bézout আর gcd দুটোই যাচাই করেছে) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log min(a, b))** — একদম সাধারণ Euclid-এর মতোই, কারণ ধাপের সংখ্যা হুবহু একই; শুধু প্রতি ধাপে দুটো বাড়তি coefficient হিসাব হচ্ছে (constant কাজ)। তাই 018-এর gcd যত দ্রুত, এটাও তত দ্রুত।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log min(a, b))** recursive version-এ — recursion-এর গভীরতা ধাপের সংখ্যার সমান, প্রতি call একটা stack frame। iterative version-এ মাত্র **O(1)** — গুটিকয় variable, কোনো stack নেই। বড় input হলে iterative-টা নিরাপদ।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Coefficient update সূত্র উল্টে ফেলা** — মনে রেখো `x = y1` আর `y = x1 − (a // b)·y1`; দুটো গুলিয়ে ফেললে Bézout মিলবে না।
2. **`a % b` আর `a // b` গুলিয়ে ফেলা** — recursion-এ যায় `a % b` (remainder), কিন্তু coefficient সূত্রে লাগে `a // b` (quotient)।
3. **x, y unique ভাবা** — একাধিক বৈধ জোড়া আছে; verify করতে সবসময় `a·x + b·y == g` চেক করো, নির্দিষ্ট মান নয়।
4. **Base case ভুলে যাওয়া বা ভুল লেখা** — `b == 0`-তে `(a, 1, 0)` ফেরত; এটা না থাকলে recursion থামবে না।
5. **এখনই সব মুখস্থ করার চেষ্টা** — এটা Hard আর Level 2-র সেতু; এখন idea বুঝলেই যথেষ্ট, modular inverse-এর সময় এটা স্বাভাবিকভাবে গেঁথে যাবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Linear Diophantine Equation** (