019 — Extended GCD Intro¶
এটা এই level-এর প্রথম Hard problem, আর Level 2-র দিকে একটা সেতু। ঘাবড়িও না — এখন perfection-এর দরকার নেই। শুধু "এটা সম্ভব আর কীভাবে সম্ভব" এটুকু বুঝে গেলেই যথেষ্ট; modular inverse করার সময় (Level 2) এই কৌশল আবার ফিরবে, তখন আরও অর্থবহ লাগবে। ধীরে পড়ো।
Source¶
- Original source: CP-Algorithms — Extended Euclidean algorithm
- Platform: CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
- 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
1. Problem in simple words¶
দুটো integer a আর b দেওয়া আছে। শুধু gcd(a, b) বের করলেই হবে না — এমন দুটো integer x আর y-ও খুঁজে বের করতে হবে যাতে:
উদাহরণ: a = 48, b = 18 হলে gcd = 6, আর একটা সমাধান হলো x = −1, y = 3, কারণ 48 × (−1) + 18 × 3 = −48 + 54 = 6। ঠিকঠাক!
মানে শুধু "সবচেয়ে বড় common divisor কত" নয়, "সেই divisor-কে a আর b-র একটা যোগফল হিসেবে কীভাবে সাজানো যায়" — সেই coefficient দুটো বের করাই কাজ।
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।
3. Which basic idea does this inherit from?¶
এটা সরাসরি 018 (GCD using Euclidean Algorithm)-এর উপর দাঁড়িয়ে। 018-এ আমরা শুধু সংখ্যাটা (gcd) ফেরত দিতাম; এখানে সেই একই ধাপগুলো ধরে রেখে, প্রতিবার coefficient-ও বয়ে নিয়ে যাই।
মূল পার্থক্য: 018 শুধু "কত" বলে; 019 বলে "কীভাবে a আর b মিলিয়ে সেই 'কত' বানানো যায়"। তাই 018 ভালো করে বুঝে না থাকলে আগে সেখানে এক ধাপ পিছিয়ে যাও — back-substitution আসলে সেই ধাপগুলোরই উল্টো যাত্রা।
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-টাই বলে দেয়: কোন বাটখারা কতবার, কোন পাল্লায়।
5. Visual explanation¶
প্রথমে সাধারণ Euclid নিচে নামে, তারপর আমরা coefficient নিয়ে আবার উপরে উঠি:
নিচে নামা (সাধারণ 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
মিলিয়ে দেখো:
6. Example input and output¶
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 চেক করব, ঠিক কোন জোড়া বেরিয়েছে তা নয়।
7. Brute force thinking¶
x, y কত হতে পারে না জানলে, সবচেয়ে সরল চিন্তা — প্রথমে সাধারণ gcd বের করি, তারপর x-কে একটা range-এ ঘুরিয়ে দেখি কোন x-এর জন্য (g − a·x) ঠিকঠাক b দিয়ে ভাগ যায় (তাহলেই y = (g − a·x) / b পূর্ণসংখ্যা):
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।
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 বসিয়ে সাজালে পাওয়া যায়:
তাই বড় সমস্যার উত্তর: 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-তে কাজে দেবে।
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-এর সাথে হুবহু মিলল।
12. Python solution¶
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¶
Base case — recursion থামার জায়গা। b = 0 হলে gcd = a, আর a·1 + 0·0 = a মেলে, তাই x = 1, y = 0।
ছোট সমস্যাটা আগে solve করি (ঠিক 018-এর Euclid-এর মতো নিচে নামা)। ওটা ফেরত দেয় (g, x1, y1) যেখানে b·x1 + (a % b)·y1 = g।
এই দুই লাইনই 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 করি (কারণ সমাধান একাধিক)।
14. Output walkthrough¶
চালালে যা ছাপবে:
প্রথম লাইন: 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!।
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¶
- Coefficient update সূত্র উল্টে ফেলা — মনে রেখো
x = y1আরy = x1 − (a // b)·y1; দুটো গুলিয়ে ফেললে Bézout মিলবে না। a % bআরa // bগুলিয়ে ফেলা — recursion-এ যায়a % b(remainder), কিন্তু coefficient সূত্রে লাগেa // b(quotient)।- x, y unique ভাবা — একাধিক বৈধ জোড়া আছে; verify করতে সবসময়
a·x + b·y == gচেক করো, নির্দিষ্ট মান নয়। - Base case ভুলে যাওয়া বা ভুল লেখা —
b == 0-তে(a, 1, 0)ফেরত; এটা না থাকলে recursion থামবে না। - এখনই সব মুখস্থ করার চেষ্টা — এটা Hard আর Level 2-র সেতু; এখন idea বুঝলেই যথেষ্ট, modular inverse-এর সময় এটা স্বাভাবিকভাবে গেঁথে যাবে।
18. Harder problems that inherit this idea¶
- CP-Algorithms — Linear Diophantine Equation (https://cp-algorithms.com/algebra/linear-diophantine-equation.html) —
a·x + b·y = cসমাধান, সরাসরি extended GCD-র উপর গড়া। - CP-Algorithms — Modular Multiplicative Inverse (https://cp-algorithms.com/algebra/module-inverse.html) — Level 2-তে এই কৌশল দিয়েই inverse বের হবে; এটাই আসল গন্তব্য।
- 023 (Euler Phi Basic) — এই repo-রই পরের ধাপে phi function, যা modular গণিতে extended GCD-র পাশেই কাজ করে।
19. Pattern learned¶
Extended Euclid / back-substitution — Euclid-এর ধাপ ধরে coefficient বয়ে নিয়ে a·x + b·y = gcd বের করা (Bézout's identity)। মূল reusable টুকরো: base (a, 1, 0), আর update x = y1, y = x1 − (a // b)·y1। modular inverse-এর সময় এই pattern সরাসরি ফিরবে।
20. Final summary¶
ভবিষ্যতের আমাকে এক লাইনে: "Extended GCD = সাধারণ Euclid + coefficient বয়ে আনা; base (a,1,0), update x=y1, y=x1−(a//b)·y1। 'a·x + b·y = gcd' দরকার দেখলেই এটা মনে করব — আর Level 2-তে modular inverse এখান থেকেই আসবে।"
পরের ধাপ → 020 — LCM using GCD (এবার gcd-র সহজ আত্মীয় LCM)। শিকড় → 018 — GCD using Euclidean Algorithm।
ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।
মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি করা হয়নি — বরং "common interview pattern" লেখা হয়েছে।