Problem link ও উৎস
- **Original source:** CP-Algorithms — Linear Diophantine Equation
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** gcd divisibility
- **Basic idea inherited from:** 125 (Extended Euclidean Algorithm)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তিনটা integer `a`, `b`, `c` দেওয়া আছে। খুঁজে বের করতে হবে এমন integer `x` আর `y`, যাতে এই সমীকরণটা মেলে:
```
a · x + b · y = c
```
এটাকে বলে **linear Diophantine equation** — "Diophantine" মানে আমরা শুধু **integer** সমাধান চাই (ভগ্নাংশ নয়)। দুটো প্রশ্ন:
1. সমাধান **আছে কি না**? (সব ক্ষেত্রে থাকে না!)
2. থাকলে — **একটা** সমাধান, আর সেই সাথে **সব** সমাধানের সূত্র।
মনে রেখো — এই level CP-leaning, interview-optional। কিন্তু "কখন integer সমাধান সম্ভব" এই প্রশ্নের উত্তরটা সংখ্যাতত্ত্বের একটা সুন্দর ছোট রত্ন।
### Input ও output {#6-example-input-and-output}
```text
input (a, b, c) -> output
------------------------------------------------------------------
30, 18, 12 -> (-2, 4) 30·(-2) + 18·4 = 12 ✓
30, 18, 11 -> None 11 % gcd(6) ≠ 0 -> সমাধান নেই
2, 3, 7 -> (7, -7) বা সমতুল্য 2·7 + 3·(-7) = -7? না -> দেখো নিচে
35, 15, 5 -> (1, -2) 35·1 + 15·(-2) = 5 ✓
6, 9, 15 -> (-5, 5) বা সমতুল্য 6·(-5)+9·5 = 15 ✓
```
খেয়াল করো: `2x + 3y = 7`-এ gcd(2, 3) = 1, আর 7 % 1 = 0 — তাই সমাধান আছে (যেমন x = 2, y = 1: `2·2 + 3·1 = 7`)। আমাদের সূত্র x₀·k দিয়ে অন্য একটা valid জোড়া দিতে পারে; **x, y unique নয়** — তাই যেকোনো জোড়া `a·x + b·y == c` মেলালেই সঠিক। আর `30x + 18y = 11`-এ 11, 6-এর গুণিতক নয় → **None** (সমাধান নেই)। এটাই সবচেয়ে গুরুত্বপূর্ণ edge case।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার কাছে দুই ধরনের কয়েন আছে — `a` টাকার আর `b` টাকার। তুমি ঠিক `c` টাকা বানাতে চাও। কিন্তু একটা মোচড় আছে: কয়েন তুমি **যোগও** করতে পারো, আবার কাউকে **ফেরতও** দিতে পারো (negative = ফেরত)।
- যদি দুই কয়েনের "সবচেয়ে ছোট ধাপ" (gcd) হয় 5 টাকা, তাহলে তুমি শুধু 5-এর গুণিতক বানাতে পারবে — 5, 10, 15, ... । 12 টাকা বানানো **অসম্ভব**, কারণ 12 ÷ 5-এ ভাগশেষ থাকে।
- কিন্তু c যদি 5-এর গুণিতক হয় (যেমন 20), তাহলে সম্ভব — আর সম্ভব **অসংখ্যভাবে**: একটা সমাধান পেলে কিছু a-কয়েন বেশি দিয়ে কিছু b-কয়েন কম দিলেই আরেকটা সমাধান।
সেই "gcd ভাগ করে কি না" চেকটাই solvability; আর "অসংখ্যভাবে" অংশটাই solution family।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **125 (Extended Euclidean Algorithm)**-এর উপর দাঁড়ানো। 125 আমাদের দিয়েছিল x₀, y₀ যাতে `a·x₀ + b·y₀ = gcd(a, b)`। Diophantine সেই ছোট জয়টাকে scale করে:
```text
a·x₀ + b·y₀ = g (125 থেকে)
দুপাশে (c/g) গুণ:
a·(x₀·c/g) + b·(y₀·c/g) = c
⇒ x = x₀·(c/g), y = y₀·(c/g)
```
মানে 125 না বুঝে 126-এ ঢোকা যায় না — extended Euclid-ই এর ইঞ্জিন। আর এর উপরে দাঁড়াবে CRT (127), যেখানে দুটো congruence merge করতে এই একই combination-চিন্তা লাগে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea একটাই বাক্যে — **solvable ⟺ gcd(a, b) ভাগ করে c-কে**:
```
a·x + b·y = c এর integer সমাধান আছে ⟺ gcd(a, b) | c
```
কেন? কারণ `a·x + b·y` যাই হোক না কেন, সেটা সবসময় `gcd(a, b)`-এর গুণিতক (g যেহেতু a, b দুটোকেই ভাগ করে, সে তাদের যেকোনো combination-কেও ভাগ করে)। তাই c যদি g-এর গুণিতক না হয়, সমাধান অসম্ভব। আর হলে — extended Euclid (125) থেকে `a·x₀ + b·y₀ = g` পেয়ে দুপাশে `c/g` গুণ করলেই এক সমাধান। এই level CP-leaning হলেও এই divisibility শর্তটাই পুরো problem-এর হৃদয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
extended Euclid ছাড়া প্রথম যে idea আসে — **একটা variable ঘুরিয়ে অন্যটা মিলে যায় কিনা দেখা**। ধরো x-কে একটা range-এ ঘোরাই; প্রতিটা x-এর জন্য চেক করি `(c − a·x)` কি b দিয়ে নিঃশেষে ভাগ যায় — গেলে y = `(c − a·x) // b`:
```python
def diophantine_brute(a, b, c, search=2000):
for x in range(-search, search + 1):
rem = c - a * x
if b != 0 and rem % b == 0:
return x, rem // b
return None
```
ছোট সংখ্যায় এটা একটা valid (x, y) খুঁজে দেয়। "কোনোভাবে হলেও হলো" — শুরুর জন্য ঠিক আছে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
দুটো সমস্যা। এক — **range কত বড় নেব** তার নিশ্চয়তা নেই; সমাধানের x বিশাল (যেমন কোটির ঘরে) হতে পারে, তখন ছোট search window-তে মিস করে ভুল করে "None" বলবে। দুই — window বড় করলে loop লম্বা হয়, O(search) সময়।
```text
সমাধানের x ছোট (|x| < 2000): brute force পায়, কিন্তু ধীর
সমাধানের x বিশাল (10⁹): brute force হয় miss করে, নয় কোটি বার loop
extended Euclid: সবসময়, O(log min(a,b)) ধাপে সরাসরি x₀
```
মূল কথা: brute force-এর কোনো **নিশ্চয়তা** নেই (ঠিক window না নিলে ভুল), আর বড় সমাধানে ধীর। অথচ extended Euclid গণিতগতভাবে নিশ্চিত করে এক সমাধান দেয়, log ধাপে।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight দুই অংশে:
**অংশ ১ — solvability আগে যাচাই করো।** `g = gcd(a, b)` বের করে দেখো `c % g == 0` কিনা। না হলে সোজা "None" — আর এক লাইনও কোড লাগে না। এই শর্তটাই algorithm-এর প্রথম লাইন।
**অংশ ২ — extended Euclid দিয়ে scale করো।** 125 থেকে `a·x₀ + b·y₀ = g` পাও, তারপর `k = c // g` দিয়ে গুণ:
```text
x = x₀ · k, y = y₀ · k
```
ব্যস, এক সমাধান তৈরি। আর সব সমাধান চাইলে পরিবার:
```text
x = x₀·k + t·(b // g)
y = y₀·k − t·(a // g) t = যেকোনো integer
```
এই family-র সৌন্দর্য: t বদলালে `a·x` যতটা বাড়ে, `b·y` ঠিক ততটা কমে — তাই যোগফল সবসময় c।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **"কখন সমাধান সম্ভব?" — এই গোটা প্রশ্নের উত্তর মাত্র একটা divisibility চেক: `c % gcd(a, b) == 0`।**
brute force পুরো range চষছিল আদৌ সমাধান আছে কিনা জানতেও; tweak হলো — খোঁজার আগেই gcd দিয়ে এক লাইনে রায় দাও। আর থাকলে, খোঁজা লাগে না — 125-এর x₀, y₀-কে `c/g` দিয়ে গুণ করলেই হাতে এক সমাধান। অনিশ্চিত O(search) থেকে নিশ্চিত O(log min(a, b))-এ নেমে এল।
### ছবিতে বোঝা {#5-visual-explanation}
`30x + 18y = 12` সমাধান করি। আগে solvability, তারপর এক সমাধান, তারপর পরিবার:
```text
ধাপ 1 — solvability:
gcd(30, 18) = 6, c = 12, 12 % 6 = 0 -> সমাধান আছে ✓
ধাপ 2 — extended Euclid (125 থেকে):
30·(−1) + 18·(2) = 6 -> x₀ = −1, y₀ = 2, g = 6
ধাপ 3 — c/g দিয়ে scale (k = 12 / 6 = 2):
x = x₀·k = −1·2 = −2
y = y₀·k = 2·2 = 4
যাচাই: 30·(−2) + 18·(4) = −60 + 72 = 12 ✓
ধাপ 4 — পুরো পরিবার (t = যেকোনো integer):
x = −2 + t·(18/6) = −2 + 3t
y = 4 − t·(30/6) = 4 − 5t
t = 1: x = 1, y = −1 -> 30·1 + 18·(−1) = 12 ✓
t = 2: x = 4, y = −6 -> 30·4 + 18·(−6) = 12 ✓
```
দাঁড়িপাল্লার ছবি: x-কে `b/g = 3` বাড়ালে যোগফলে `30·3 = 90` বাড়ে; y-কে `a/g = 5` কমালে `18·5 = 90` কমে — দুই পাশ সমান, যোগফল অপরিবর্তিত c। তাই অসীম সমাধান।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`30x + 18y = 12`-এর জন্য `diophantine(30, 18, 12)`:
| step | কী করছি | মান |
| --- | --- | --- |
| 1 | g, x₀, y₀ = ext_gcd(30, 18) | g = 6, x₀ = −1, y₀ = 2 |
| 2 | c % g চেক: 12 % 6 | 0 → সমাধান আছে |
| 3 | k = c // g = 12 // 6 | k = 2 |
| 4 | x = x₀·k = −1·2 | x = −2 |
| 5 | y = y₀·k = 2·2 | y = 4 |
| 6 | যাচাই: 30·(−2) + 18·4 | −60 + 72 = 12 ✓ |
পরিবার বের করতে (যদি সব সমাধান চাই):
| step | সূত্র | মান |
| --- | --- | --- |
| 7 | b // g = 18 // 6 | 3 (x-এর ধাপ) |
| 8 | a // g = 30 // 6 | 5 (y-এর ধাপ) |
| 9 | t = 1: x = −2 + 3, y = 4 − 5 | (1, −1) → 30·1 + 18·(−1) = 12 ✓ |
দেখো — base solution (−2, 4) থেকে t বদলে অন্য সমাধান (1, −1) পেলাম, যোগফল দুটোতেই 12।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import gcd
def ext_gcd(a, b):
"""a*x + b*y = gcd(a, b) এর (g, x, y) ফেরত দেয় (125 থেকে)।"""
if b == 0:
return a, 1, 0
g, x1, y1 = ext_gcd(b, a % b)
return g, y1, x1 - (a // b) * y1
def diophantine(a, b, c):
"""a*x + b*y = c এর একটা (x, y) ফেরত দেয়, সমাধান না থাকলে None।"""
g, x0, y0 = ext_gcd(a, b)
if c % g != 0:
return None # gcd(a,b) ভাগ করে না c-কে
k = c // g
return x0 * k, y0 * k
def diophantine_family(a, b, c, t):
"""একই সমীকরণের t-তম সমাধান (পরিবারের যেকোনো সদস্য)।"""
base = diophantine(a, b, c)
if base is None:
return None
x0, y0 = base
g = gcd(a, b)
return x0 + t * (b // g), y0 - t * (a // g)
# --- ছোট test গুলো (সব pass করা উচিত) ---
def verify(a, b, c, must_exist):
sol = diophantine(a, b, c)
if not must_exist:
assert sol is None, f"সমাধান থাকার কথা না: {a},{b},{c}"
return
assert sol is not None, f"সমাধান থাকার কথা: {a},{b},{c}"
x, y = sol
assert a * x + b * y == c, f"identity ভুল: {a},{b},{c} -> {sol}"
# পরিবারের কয়েকটা সদস্যও যাচাই
for t in (-3, -1, 0, 1, 2, 5):
fx, fy = diophantine_family(a, b, c, t)
assert a * fx + b * fy == c, f"family ভুল: {a},{b},{c}, t={t}"
verify(30, 18, 12, True)
verify(30, 18, 11, False) # 11, 6-এর গুণিতক নয়
verify(35, 15, 5, True)
verify(2, 3, 7, True)
verify(6, 9, 15, True)
verify(6, 9, 14, False) # 14, 3-এর গুণিতক নয়
verify(1, 1, 100, True)
verify(12, 8, 0, True) # c = 0 -> (0, 0) সবসময় সমাধান
x, y = diophantine(30, 18, 12)
assert 30 * x + 18 * y == 12
print(diophantine(30, 18, 12)) # (-2, 4)
print(diophantine(30, 18, 11)) # None
print(diophantine_family(30, 18, 12, 1)) # (1, -1)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def diophantine(a, b, c):
g, x0, y0 = ext_gcd(a, b)
```
প্রথমে 125-এর extended Euclid ডাকছি — পাচ্ছি g = gcd, আর x₀, y₀ যাতে `a·x₀ + b·y₀ = g`।
```
if c % g != 0:
return None
```
solvability-র মূল চেক — c যদি g-এর গুণিতক না হয়, integer সমাধান অসম্ভব, সোজা None। এটাই algorithm-এর প্রথম ও সবচেয়ে গুরুত্বপূর্ণ লাইন।
```
k = c // g
return x0 * k, y0 * k
```
scale করছি — `a·x₀ + b·y₀ = g`-এর দুপাশে k = c/g গুণ করলে `a·(x₀k) + b·(y₀k) = c`। তাই (x₀·k, y₀·k) একটা সমাধান।
```
def diophantine_family(a, b, c, t):
...
return x0 + t * (b // g), y0 - t * (a // g)
```
পরিবারের t-তম সদস্য — base solution থেকে x-কে `t·(b/g)` বাড়িয়ে, y-কে `t·(a/g)` কমিয়ে। এই বাড়া-কমা ঠিক সমান ওজনের, তাই যোগফল c অপরিবর্তিত।
বাকি `verify` function ও `assert` লাইনগুলো নিজেরাই যাচাই করে — solvable হলে identity মেলে কিনা, পরিবারের সদস্যরাও মেলে কিনা, আর unsolvable হলে সত্যিই None আসে কিনা। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
(-2, 4)
None
(1, -1)
সব test pass!
```
প্রথম লাইন `diophantine(30, 18, 12)` → (−2, 4), যা `30·(−2) + 18·4 = 12` মেলায়। দ্বিতীয় `diophantine(30, 18, 11)` → None, কারণ 11, gcd 6-এর গুণিতক নয়। তৃতীয় `diophantine_family(30, 18, 12, 1)` → (1, −1), পরিবারের আরেক সদস্য (`30·1 + 18·(−1) = 12`)। আগের সব assert চুপচাপ pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log min(a, b))** — পুরো খরচ extended Euclid-এর, যা Euclid-এর মতোই logarithmic। তার পরে শুধু একটা ভাগ, একটা গুণ, একটা mod — সব O(1)। তাই brute force-এর অনিশ্চিত O(search)-এর তুলনায় এটা নিশ্চিত ও দ্রুত।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log min(a, b))** recursive ext_gcd-এর জন্য (call stack); iterative ext_gcd ব্যবহার করলে **O(1)**। মূল diophantine function নিজে কোনো extra array রাখে না, শুধু গুটিকয় variable।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **solvability চেক না করেই solution খোঁজা** — সবচেয়ে কমন। `c % g != 0` হলে সমাধান নেই; এই লাইন বাদ দিলে ভুল উত্তর। আগে শর্ত, পরে খোঁজা।
2. **`g` দিয়ে নয়, ভুল সংখ্যা দিয়ে scale** — k হলো `c // g`, `c // a` বা অন্য কিছু নয়।
3. **family-র সূত্রে a, b উল্টে ফেলা** — x বাড়ে `b/g` দিয়ে, y কমে `a/g` দিয়ে (cross করা)। উল্টে ফেললে যোগফল আর c থাকে না।
4. **একটা সমাধানকেই একমাত্র ভাবা** — অসীম সমাধান আছে; reference-এর সাথে হুবহু না মিললেও identity মিললেই সঠিক।
5. **a বা b শূন্য ভুলে যাওয়া** — যেমন a = 0 হলে সমীকরণ `b·y = c`, আলাদা করে ভাবা ভালো (যদিও ext_gcd এ-ও সামলায়, brute force সামলায় না)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Stick Lengths / coin-style** আর অনেক Codeforces problem যেখানে "ঠিক c বানানো যায় কিনা integer combination-এ" — সরাসরি Diophantine solvability।
- **Codeforces — problemset-এ "ax + by = c" ধরনের constructive problem** (