Problem link ও উৎস
- **Original source:** CP-Algorithms — Chinese Remainder Theorem
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** modulus merge
- **Basic idea inherited from:** 125 (Extended Euclidean Algorithm)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো শর্ত (congruence) দেওয়া আছে একটা অজানা সংখ্যা `x`-এর উপর:
```
x ≡ a1 (mod m1) (x-কে m1 দিয়ে ভাগ করলে ভাগশেষ a1)
x ≡ a2 (mod m2) (x-কে m2 দিয়ে ভাগ করলে ভাগশেষ a2)
```
খুঁজে বের করতে হবে এমন একটা `x` যেটা **দুটো শর্তই একসাথে** মানে। basic CRT ধরে নেয় `m1` আর `m2` **coprime** (gcd = 1) — তখন `0` থেকে `m1·m2 − 1`-এর মধ্যে উত্তর ঠিক **একটাই**, আর পুরো উত্তরটা হয় `x ≡ ans (mod m1·m2)`।
মনে রেখো — এই level CP-leaning, interview-optional। কিন্তু CRT-র গল্পটা সংখ্যাতত্ত্বের সবচেয়ে মার্জিত ফলাফলগুলোর একটা।
### Input ও output {#6-example-input-and-output}
```text
input (a1, m1, a2, m2) -> output (ans, mod)
----------------------------------------------------------------
2, 3, 3, 5 -> (8, 15) 8%3=2 ✓, 8%5=3 ✓
2, 3, 2, 7 -> (2, 21) 2%3=2 ✓, 2%7=2 ✓
1, 4, 2, 9 -> (29, 36) 29%4=1 ✓, 29%9=2 ✓
0, 5, 0, 7 -> (0, 35) 0 দুটোই মানে
3, 5, 1, 11 -> (23, 55) 23%5=3 ✓, 23%11=1 ✓
```
খেয়াল করো: **basic CRT ধরে নেয় m1, m2 coprime** — যেমন (3, 5), (4, 9), (5, 11)। coprime না হলে (যেমন m1 = 4, m2 = 6) এই সরল সূত্র চলে না; তখন general CRT লাগে (নিচে common mistakes-এ)। উত্তর সবসময় `0` থেকে `m1·m2 − 1`-এর মধ্যে normalize করা হয়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ঘটনা ঘটেছিল, কিন্তু সঠিক সময় ভুলে গেছ। হাতে দুটো ভাঙা ঘড়ি:
- একটা **3-ঘণ্টার ঘড়ি** (শুধু 0, 1, 2 দেখায়) — সেটায় কাঁটা ছিল 2-এ → `x ≡ 2 (mod 3)`
- একটা **5-ঘণ্টার ঘড়ি** (0 থেকে 4) — সেটায় কাঁটা ছিল 3-এ → `x ≡ 3 (mod 5)`
আলাদাভাবে প্রতিটা ঘড়ি অনেক সময়ের সাথে মেলে। কিন্তু **দুটো একসাথে** মেলানোর সময়? দুই ঘড়ির "মোট চক্র" হলো 3 × 5 = 15 ঘণ্টা (যেহেতু coprime), আর সেই 15 ঘণ্টার মধ্যে দুটো reading একসাথে মেলে ঠিক **একবার** — সময়টা 8। তার পরের বার আবার 8 + 15 = 23, তারপর 38... ।
CRT হলো সেই কৌশল যা দুই ভাঙা ঘড়ির আংশিক তথ্য জুড়ে আসল সময়টা (mod 15) বের করে দেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **125 (Extended Euclidean Algorithm)**। CRT-র গোটা হিসাবের কেন্দ্রে `m1`-এর inverse mod `m2` — আর coprime দুটো সংখ্যার inverse বের করার একমাত্র সাধারণ হাতিয়ার extended Euclid (`m1·p + m2·q = 1` থেকে `p = m1⁻¹ mod m2`)।
তাই শিকড়ের শৃঙ্খল: 125 (ext Euclid) → 127 (CRT)। আর 126 (Diophantine)-এর "combination-এ ঠিক মান বানানো" চিন্তাও এখানে কাজে লাগে। মনে রাখো — README-র recommended order-এ 127 ঠিক 125-এর পরেই, কারণ এটা ext-Euclid-এর সবচেয়ে সরাসরি প্রয়োগ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **দুটো আলাদা modulus-কে এক বড় modulus-এ merge করা**। যদি m1, m2 coprime হয়, তবে দুটো ভিন্ন ভাগশেষ-শর্ত একসাথে ঠিক একটা সমাধান শ্রেণি (mod m1·m2) তৈরি করে — এটাই Chinese Remainder Theorem।
কীভাবে বের করি? `x = a1 + m1·t` লিখি (এটা প্রথম শর্ত আপনিই মানে, যেকোনো integer t-তে)। তারপর দ্বিতীয় শর্তে বসাই:
```
a1 + m1·t ≡ a2 (mod m2)
m1·t ≡ (a2 − a1) (mod m2)
t ≡ (a2 − a1) · m1⁻¹ (mod m2)
```
এখানে `m1⁻¹ (mod m2)` লাগে — আর সেটা দেয় আমাদের পুরোনো বন্ধু **extended Euclid** (125)। এই level CP-leaning হলেও দেখো, পুরোটাই 125-এর উপর দাঁড়ানো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
inverse-টিন্স ছাড়া প্রথম idea — **0 থেকে m1·m2 − 1 পর্যন্ত প্রতিটা সংখ্যা চেক করা**, কোনটা দুটো শর্তই মানে:
```python
def crt_brute(a1, m1, a2, m2):
for x in range(m1 * m2):
if x % m1 == a1 % m1 and x % m2 == a2 % m2:
return x, m1 * m2
return None
```
ছোট moduli-তে (3, 5) এটা সহজেই 8 খুঁজে দেয়। coprime হলে সমাধান নিশ্চিত আছে — তাই এটা সবসময় উত্তর পায়। শুরুর জন্য একদম ঠিক।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে `m1 · m2` বার। ছোট moduli-তে কিছুই না, কিন্তু moduli বড় হলে সর্বনাশ:
```text
m1, m2 ছোট (3, 5): 15 বার loop — চোখের পলক
m1, m2 = 10⁶, 10⁶: 10¹² বার loop — কয়েক দিন!
CRT merge (inverse): O(log m) — মুহূর্তে
```
দুটো বড় modulus-এ brute force কার্যত অচল। অথচ আসল CRT merge শুধু একটা extended Euclid (log ধাপ) আর কয়েকটা গুণ — তাই moduli যত বড়ই হোক, প্রায় তাৎক্ষণিক।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **খোঁজার দরকার নেই, সরাসরি হিসাব করা যায়।** ধাপগুলো:
```text
1. x = a1 + m1·t ধরো (প্রথম শর্ত আপনিই মানা)
2. দ্বিতীয় শর্তে বসাও: a1 + m1·t ≡ a2 (mod m2)
3. m1·t ≡ (a2 − a1) (mod m2)
4. t ≡ (a2 − a1) · inv(m1, m2) (mod m2) [extended Euclid!]
5. x = a1 + m1·t, নতুন modulus = m1·m2
6. উত্তর normalize: x % (m1·m2)
```
পুরো ব্যাপারটা একটা inverse আর কয়েকটা গুণ-যোগে শেষ। inverse-টাই একমাত্র "ভারী" ধাপ, আর সেটা 125-এর ext-gcd দিয়ে O(log m)। coprime হওয়ায় inverse সবসময় থাকে — তাই merge সবসময় সফল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **`x = a1 + m1·t` লিখে ফেললে প্রথম শর্ত আর ভাবতে হয় না — শুধু দ্বিতীয় শর্ত থেকে t বের করলেই হলো।**
brute force দুটো শর্ত একসাথে মেলাতে পুরো range চষছিল; tweak হলো — একটা শর্তকে x-এর গঠনে (`a1 + m1·t`) ঢুকিয়ে দাও, তখন বাকি থাকে শুধু একটা variable t, আর একটা congruence — যা inverse দিয়ে এক ধাপে solve হয়। দুই শর্তের যুগপৎ খোঁজা থেকে এক variable-এর সরল সমাধানে নেমে এল।
### ছবিতে বোঝা {#5-visual-explanation}
`x ≡ 2 (mod 3)` আর `x ≡ 3 (mod 5)` মেলাই — আগে চোখে, তারপর সূত্রে:
```text
চোখে — দুই তালিকা মিলিয়ে দেখা:
x ≡ 2 (mod 3): 2, 5, 8, 11, 14, 17, ...
x ≡ 3 (mod 5): 3, 8, 13, 18, ...
▲
প্রথম মিল x = 8, পরেরটা 8 + 15 = 23 ...
উত্তর: x ≡ 8 (mod 15)
সূত্রে (merge):
x = a1 + m1·t = 2 + 3t [প্রথম শর্ত মানা]
দ্বিতীয় শর্তে: 2 + 3t ≡ 3 (mod 5)
3t ≡ 1 (mod 5)
t ≡ 1 · (3⁻¹ mod 5) (mod 5)
3⁻¹ mod 5 = 2 [কারণ 3·2 = 6 ≡ 1]
t ≡ 1·2 = 2 (mod 5)
x = 2 + 3·2 = 8 ✓
নতুন modulus = m1·m2 = 15
```
লক্ষ করো — `3⁻¹ mod 5` বের করতেই extended Euclid-এর দরকার। আর উত্তর `8` দুই তালিকার প্রথম মিল-এর সাথে হুবহু মিলল।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`crt(2, 3, 3, 5)` — মানে `x ≡ 2 (mod 3)`, `x ≡ 3 (mod 5)`:
| step | কী করছি | মান |
| --- | --- | --- |
| 1 | g, p, q = ext_gcd(m1, m2) = ext_gcd(3, 5) | g = 1, p = 2, q = −1 (3·2 + 5·(−1) = 1) |
| 2 | p হলো m1⁻¹ mod m2 → 3⁻¹ mod 5 | p = 2 (যেহেতু 3·2 = 6 ≡ 1 mod 5) |
| 3 | diff = a2 − a1 = 3 − 2 | 1 |
| 4 | t = (diff · p) % m2 = (1·2) % 5 | t = 2 |
| 5 | x = a1 + m1·t = 2 + 3·2 | x = 8 |
| 6 | mod = m1·m2 = 3·5 | 15 |
| 7 | normalize: 8 % 15 | 8 |
| 8 | যাচাই: 8 % 3 = 2 ✓, 8 % 5 = 3 ✓ | (8, 15) |
চূড়ান্ত: `(8, 15)`। দুই ঘড়ির reading মিলে গেল ঠিক 8-এ — section 5-এর চোখে-দেখা মিলের সাথে হুবহু।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
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 crt(a1, m1, a2, m2):
"""x ≡ a1 (mod m1), x ≡ a2 (mod m2) merge করে (ans, m1*m2)।
ধরে নেয় gcd(m1, m2) = 1 (basic CRT)।"""
g, p, _ = ext_gcd(m1, m2)
assert g == 1, "basic CRT-তে m1, m2 coprime হতে হবে"
mod = m1 * m2
diff = (a2 - a1) % m2
t = (diff * p) % m2 # p = m1⁻¹ mod m2
x = (a1 + m1 * t) % mod
return x, mod
def crt_list(remainders, moduli):
"""একাধিক congruence জোড়ায় জোড়ায় merge করে।"""
cur_a, cur_m = remainders[0], moduli[0]
for a, m in zip(remainders[1:], moduli[1:]):
cur_a, cur_m = crt(cur_a, cur_m, a, m)
return cur_a, cur_m
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def verify(a1, m1, a2, m2):
ans, mod = crt(a1, m1, a2, m2)
assert mod == m1 * m2, f"mod ভুল: {a1,m1,a2,m2}"
assert ans % m1 == a1 % m1, f"শর্ত 1 ভাঙল: {a1,m1,a2,m2} -> {ans}"
assert ans % m2 == a2 % m2, f"শর্ত 2 ভাঙল: {a1,m1,a2,m2} -> {ans}"
assert 0 <= ans < mod, f"range বাইরে: {ans}"
verify(2, 3, 3, 5)
verify(2, 3, 2, 7)
verify(1, 4, 2, 9)
verify(0, 5, 0, 7)
verify(3, 5, 1, 11)
verify(10, 13, 4, 17)
# একাধিক congruence: x ≡ 2(3), 3(5), 2(7) -> CSES classic
multi, mmod = crt_list([2, 3, 2], [3, 5, 7])
assert multi % 3 == 2 and multi % 5 == 3 and multi % 7 == 2
assert mmod == 3 * 5 * 7
# brute force-এর সাথে cross-check
def crt_brute(a1, m1, a2, m2):
for x in range(m1 * m2):
if x % m1 == a1 % m1 and x % m2 == a2 % m2:
return x
return None
for (a1, m1, a2, m2) in [(2,3,3,5), (1,4,2,9), (3,5,1,11), (2,3,2,7)]:
assert crt(a1, m1, a2, m2)[0] == crt_brute(a1, m1, a2, m2)
print(crt(2, 3, 3, 5)) # (8, 15)
print(crt(1, 4, 2, 9)) # (29, 36)
print(crt_list([2, 3, 2], [3, 5, 7])) # (23, 105)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def crt(a1, m1, a2, m2):
g, p, _ = ext_gcd(m1, m2)
assert g == 1, "basic CRT-তে m1, m2 coprime হতে হবে"
```
extended Euclid দিয়ে `m1·p + m2·q = g` পাচ্ছি। coprime হলে g = 1, আর তখন `p` হলো `m1`-এর inverse mod m2। coprime না হলে assert থামিয়ে দেয় (basic CRT-র সীমা)।
```
mod = m1 * m2
diff = (a2 - a1) % m2
t = (diff * p) % m2
```
merge-এর গণিত: `m1·t ≡ (a2 − a1) (mod m2)` থেকে `t = (a2 − a1)·m1⁻¹ mod m2`। diff-কে আগে `% m2` করছি যাতে negative না হয়।
```
x = (a1 + m1 * t) % mod
return x, mod
```
`x = a1 + m1·t` প্রথম শর্ত মানে, আর t-এর হিসাবে দ্বিতীয়টাও। শেষে `% mod` দিয়ে `0` থেকে `m1·m2 − 1`-এ normalize।
```
def crt_list(remainders, moduli):
...
cur_a, cur_m = crt(cur_a, cur_m, a, m)
```
দুটোর বেশি congruence? একটা একটা করে আগেরটার সাথে merge — প্রতি merge-এ modulus গুণ হয়ে বড় হয়। এভাবে CSES-এর মতো অনেক congruence-ও সামলানো যায়।
বাকি `verify`, brute-force cross-check আর `assert` লাইনগুলো নিশ্চিত করে — উত্তর দুটো শর্তই মানে, range-এ আছে, আর brute force-এর সাথে হুবহু মেলে। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
(8, 15)
(29, 36)
(23, 105)
সব test pass!
```
প্রথম লাইন `crt(2, 3, 3, 5)` → (8, 15): `8 % 3 = 2`, `8 % 5 = 3`। দ্বিতীয় `crt(1, 4, 2, 9)` → (29, 36): `29 % 4 = 1`, `29 % 9 = 2`। তৃতীয় `crt_list([2,3,2], [3,5,7])` → (23, 105): `23 % 3 = 2`, `23 % 5 = 3`, `23 % 7 = 2` — তিন শর্তই মানে, modulus 3·5·7 = 105। সব assert ও brute-force cross-check pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log min(m1, m2))** এক জোড়া merge-এর জন্য — পুরো খরচ extended Euclid-এর (inverse বের করা)। বাকি সব O(1) গুণ-যোগ। **n টা congruence** merge করলে n−1 বার merge, তাই O(n · log M)। brute force-এর O(m1·m2)-এর তুলনায় বিশাল লাফ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(log min(m1, m2))** recursive ext_gcd-এর call stack-এর জন্য; iterative ext_gcd নিলে **O(1)**। crt নিজে কোনো বড় array রাখে না, শুধু কয়েকটা variable। crt_list-ও running pair (cur_a, cur_m) ছাড়া বাড়তি কিছু রাখে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **moduli coprime কি না না দেখা** — সবচেয়ে কমন। basic CRT শুধু `gcd(m1, m2) = 1` হলে চলে। coprime না হলে general CRT লাগে: সমাধান থাকে ⟺ `(a1 − a2)` কে `gcd(m1, m2)` ভাগ করে; নতুন modulus হয় lcm(m1, m2)।
2. **diff বা t negative রেখে দেওয়া** — `(a2 − a1)` negative হতে পারে; `% m2` দিয়ে সবসময় positive-এ আনো, নইলে ভুল x।
3. **inverse ভুল দিক থেকে নেওয়া** — `p` হলো `m1⁻¹ mod m2` (ext_gcd(m1, m2)-এর প্রথম সহগ), `m2⁻¹` নয়।
4. **চূড়ান্ত উত্তর normalize না করা** — `% (m1·m2)` না করলে উত্তর range-এর বাইরে চলে যেতে পারে।
5. **overflow ভাবা (অন্য ভাষায়)** — Python-এ বড় সংখ্যা auto-handle হয়, কিন্তু C++/Java-তে `m1 * t` বা `m1 * m2` overflow করতে পারে; সেখানে __int128 বা mulmod লাগে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Chinese Remainder Theorem-ধাঁচের problem** আর Mathematics section (