Problem link ও উৎস
- **Original source:** Classic exercise (modular division via inverse)
- **Platform:** Classic exercise — CP-তে নিত্য; CP-Algorithms module-inverse page-এর সরাসরি প্রয়োগ
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Medium
- **Pattern:** multiply by inverse (modular division)
- **Basic idea inherited from:** 032 — Modular Inverse Basic (inverse দিয়ে ভাগ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো সংখ্যা `a` (ভাজ্য) আর `b` (ভাজক) আর একটা **prime** `p` দেওয়া (`b` যেন `p`-এর গুণিতক না হয়)। বের করতে হবে **`(a / b) mod p`** — মানে এমন একটা মান যা mod-জগতে "a-কে b দিয়ে ভাগ"-এর সঠিক প্রতিনিধি।
সমস্যা: mod-এ সরাসরি `(a % p) / (b % p)` চলে না (concept-notes-এ দেখেছ — মেলে না)। সমাধান: ভাগের বদলে `b`-এর inverse দিয়ে গুণ — `a × b⁻¹ % p`।
### Input ও output {#6-example-input-and-output}
```text
a b p (prime) -> (a/b) mod p check (result × b % p == a % p)
----------------------------------------------------------------------
6 3 7 -> 2 2×3=6 ✓
10 2 7 -> 5 5×2=10≡3, আর 10%7=3 ✓
1 3 7 -> 5 5×3=15≡1 ✓ (= inverse(3))
8 4 7 -> 2 2×4=8≡1, 8%7=1 ✓
5 5 13 -> 1 যেকোনো/নিজে = 1
14 7 1000000007 -> 2 (বড় prime-এও)
```
খেয়াল করো result সবসময় 0..p−1-এর মধ্যে। আর যাচাইয়ের নিয়ম: `(result × b) % p == a % p` — সত্যিকার ভাগ হলে এটা মিলবেই। `b` যদি `p`-এর গুণিতক হয় (inverse নেই), ভাগ অসংজ্ঞায়িত।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা দেশে **ভাগ করার যন্ত্রই নেই** — শুধু গুণ করা যায়। তুমি 6 টাকা 3 জনের মধ্যে ভাগ করতে চাও। ভাগ যন্ত্র নেই, তাই কী করবে?
তুমি খুঁজবে "3-এর উল্টো জিনিস" — এমন একটা সংখ্যা যাকে 3 দিয়ে গুণ করলে 1 হয় (সাধারণ গণিতে 1/3)। তারপর 6-কে সেই উল্টো দিয়ে গুণ করলেই ভাগের উত্তর। mod-জগতেও তাই: ভাগ যন্ত্র নেই, কিন্তু `b`-এর "উল্টো" (inverse) দিয়ে গুণ করলেই ভাগ হয়ে যায়। inverse-ই সেই হারানো ভাগ-যন্ত্রের বিকল্প।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **032 — Modular Inverse Basic** থেকে। 032-এ শিখেছ `b⁻¹ = b^(p−2) mod p`; এই note সেটা ব্যবহার করে আসল ভাগ করে। 032 ছিল "inverse কী", 035 হলো "inverse দিয়ে কী করি"।
পেছনে 028 (modular multiplication — কারণ ভাগ এখন গুণ) আর 026 (congruence — কারণ result যাচাই করি `result × b ≡ a` দিয়ে)। মানে inverse + গুণ = mod-জগতে ভাগ; দুই চেনা জিনিসের জোট।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **division as multiplication by inverse**:
`(a / b) mod p = (a × b⁻¹) mod p`, যেখানে `b⁻¹` হলো b-এর modular inverse
সাধারণ গণিতেও "a ÷ b" মানে আসলে "a × (1/b)"। mod-জগতে `1/b` নেই, কিন্তু তার বদলি `b⁻¹` আছে (032-এর Fermat inverse, `b^(p−2) mod p`)। তাই:
`(a / b) mod p = a × b^(p−2) mod p`
শর্ত: ভাগটা যেন "নিখুঁত" অর্থে valid হয় — অর্থাৎ `b`-এর inverse থাকতে হবে, মানে `gcd(b, p) = 1` (prime p-তে b যেন p-এর গুণিতক না হয়)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
কী খুঁজছি? এমন `x` (0..p−1) যাতে `x × b ≡ a (mod p)`। সব `x` চেষ্টা করো:
```python
def mod_div_brute(a, b, p):
a %= p
b %= p
if b == 0:
raise ValueError("0-এর modular inverse নেই")
for x in range(p):
if (x * b) % p == a:
return x
return None # বৈধ prime p ও nonzero b-তে এখানে পৌঁছাবে না
```
ছোট `p`-তে সঠিক আর স্পষ্ট — সংজ্ঞাটাই সরাসরি যাচাই করছে। সমস্যা: loop চলে p পর্যন্ত।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে p বার। `p = 10⁹+7` হলে প্রায় 1 বিলিয়ন iteration — একটা ভাগেই সেকেন্ড গড়ায়। CP/interview-তে অচল।
```text
p = 10^9+7 হলে:
brute (O(p)): ~10^9 বার চেষ্টা -> প্রতি ভাগে সেকেন্ড
inverse (O(log p)): ~30 বার গুণ -> ঝটপট
log2(10^9) ≈ 30 -> 1 বিলিয়ন বনাম 30
```
মূল শিক্ষা: প্রতিটা x চেষ্টা না করে, b-এর inverse এক ধাপে (Fermat, fast power) বের করে গুণো।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
inverse দিয়ে গুণ — 032-এর `mod_inverse` কাজে লাগিয়ে:
```python
def mod_inverse(b, p):
return pow(b, p - 2, p) # 032: Fermat inverse
def mod_div(a, b, p):
a %= p
b %= p
return a * mod_inverse(b, p) % p
```
দুই লাইনেই mod-জগতে ভাগ — O(log p)। `mod_inverse` ভেতরে square-and-multiply চালায়, তাই `b`-এর inverse এক লাফে।
চাইলে inline:
```python
def mod_div_inline(a, b, p):
return (a % p) * pow(b, p - 2, p) % p
```
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **mod-জগতে `a / b` মানে `a × b⁻¹` — ভাগ চিহ্নটা ভুলে গিয়ে "inverse দিয়ে গুণ" ভাবো।** `/` operator mod-এ অর্থহীন (concept-notes-এর পাল্টা উদাহরণ মনে রাখো); এই নোটের শর্তে সঠিক পদ্ধতি inverse দিয়ে গুণ।
সবচেয়ে দামি অভ্যাস: ভাগ করার পর সবসময় `(result × b) % p == a % p` দিয়ে মিলিয়ে নাও। mod-এর bug চোখে দেখা যায় না — এই যাচাইতেই ধরা পড়ে। আর মনে রাখো এটা শুধু prime p-তে সরল; non-prime হলে gcd(b, p)=1 লাগবে আর Extended GCD।
### ছবিতে বোঝা {#5-visual-explanation}
mod 7-এ "6 ভাগ 3" — inverse দিয়ে:
```text
লক্ষ্য: (6 / 3) mod 7
mod-এ ভাগ নেই, তাই:
step 1: inverse(3) mod 7 = 5 (কারণ 3×5=15≡1)
step 2: 6 × 5 % 7 = 30 % 7 = 2
Check: result × b ≡ a ? 2 × 3 = 6 ≡ 6 (mod 7) ✓
সাধারণ গণিতেও 6/3 = 2 — এখানে মিলেও গেল
```
কেন সরাসরি ভাগ চলে না — একটা পাল্টা উদাহরণ:
```text
(12 / 6) mod 4 = 2 (সত্যি)
কিন্তু ((12%4) / (6%4)) = (0 / 2) = 0 <- ভুল!
^ সরাসরি mod-করা সংখ্যায় ভাগ মেলে না
```
এই উদাহরণে gcd(6,4)=2, তাই inverse-ও নেই। `6x ≡ 12 (mod 4)`-এর উত্তর x=0 ও x=2—একটি নির্দিষ্ট modular ভাগফল বেছে নেওয়া যায় না। এই নোটের prime-modulus ও nonzero-divisor শর্তে inverse দিয়ে গুণে একটিমাত্র উত্তর পাওয়া যায়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`mod_div(6, 3, 7)`:
```text
step 0: a = 6 % 7 = 6, b = 3 % 7 = 3
```
inverse(3) mod 7 = `3^(7-2) % 7 = 3^5 % 7`, fast power-এ (5 = 101₂):
| step | exp (binary) | last bit | result | base (square হয়ে) |
| --- | --- | --- | --- | --- |
| শুরু | 101 | — | 1 | 3 |
| 1 | 101 | 1 | 1×3 % 7 = 3 | 3×3 % 7 = 2 |
| 2 | 10 | 0 | 3 | 2×2 % 7 = 4 |
| 3 | 1 | 1 | 3×4 % 7 = 5 | — |
তাই inverse(3) = **5**। এবার ভাগ:
```text
mod_div = a × inverse(b) % p = 6 × 5 % 7 = 30 % 7 = 2
```
উত্তর **2**। Check: `(2 × 3) % 7 = 6 = 6 % 7` ✓ — সত্যিকার ভাগ। আর সাধারণ গণিতেও 6/3 = 2, এখানে মিলেও গেল (যখন ভাগ "নিখুঁত")।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mod_inverse(b, p):
"""b-এর modular inverse mod p (Fermat, p prime, b % p != 0)।"""
b %= p
if b == 0:
raise ValueError("0-এর inverse নেই — ভাগ অসংজ্ঞায়িত")
return pow(b, p - 2, p)
def mod_div(a, b, p):
"""(a / b) mod p = a × b⁻¹ mod p (p prime)।"""
a %= p
return a * mod_inverse(b, p) % p
def mod_div_brute(a, b, p):
"""যাচাইয়ের জন্য সরল O(p): x × b ≡ a খুঁজি।"""
a %= p
b %= p
if b == 0:
raise ValueError("0-এর modular inverse নেই")
for x in range(p):
if (x * b) % p == a:
return x
return None
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert mod_div(6, 3, 7) == 2 # 6/3 = 2
assert mod_div(1, 3, 7) == 5 # 1/3 = inverse(3) = 5
assert mod_div(10, 2, 7) == 5 # 10×inv(2)=10×4=40≡5
assert mod_div(5, 5, 13) == 1 # নিজে/নিজে = 1
# মূল যাচাই: (result × b) ≡ a (mod p)
for a in range(0, 7):
for b in range(1, 7): # b ≠ 0 mod 7
x = mod_div(a, b, 7)
assert (x * b) % 7 == a % 7
# brute-এর সাথে মিল (ছোট prime):
for a in range(0, 13):
for b in range(1, 13):
assert mod_div(a, b, 13) == mod_div_brute(a, b, 13)
# বড় prime-এ যাচাই:
P = 1000000007
assert (mod_div(14, 7, P) * 7) % P == 14 % P
assert (mod_div(123456789, 987654321, P) * 987654321) % P == 123456789 % P
print(mod_div(6, 3, 7)) # 2
print(mod_div(1, 3, 7)) # 5
print(mod_div(14, 7, 1000000007)) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def mod_inverse(b, p):
b %= p
if b == 0:
raise ValueError(...)
return pow(b, p - 2, p)
```
032-এর Fermat inverse: `b`-কে ঘড়িতে নামাই; 0 হলে inverse নেই, তাই error (নাহলে ভাগ ভুল হতো); নাহলে `b^(p−2) mod p`।
```text
def mod_div(a, b, p):
a %= p
return a * mod_inverse(b, p) % p
```
এটাই হৃদয়: ভাগ = `a` গুণ `b`-এর inverse, তারপর `% p`। `/` চিহ্ন নেই কোথাও — পুরোটাই গুণ।
```text
for x in range(p):
if (x * b) % p == a:
return x
```
`mod_div_brute`-এ সংজ্ঞা সরাসরি: কোন `x`-এ `x × b ≡ a`। শুধু যাচাই আর বোঝার জন্য।
```text
for a in range(0, 7):
for b in range(1, 7):
x = mod_div(a, b, 7)
assert (x * b) % 7 == a % 7
```
এই double loop প্রতিটা (a, b)-র জন্য `result × b ≡ a` নিশ্চিত করছে — ভাগের সংজ্ঞাই যাচাই। আর `mod_div_brute`-এর সাথে মিলিয়ে দ্বিগুণ নিশ্চিত। বড় prime-এও একই যাচাই। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
5
2
সব test pass!
```
প্রথম লাইন `mod_div(6, 3, 7)` → 2 (6/3)। দ্বিতীয় `mod_div(1, 3, 7)` → 5 (1/3 = inverse(3))। তৃতীয় `mod_div(14, 7, 10⁹+7)` → 2 (14/7, বড় prime-এও সরল)। আগের সব `assert` (সংজ্ঞা + brute মিল + বড় prime সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log p)** — মূল খরচ `mod_inverse`-এর `pow(b, p-2, p)` (square-and-multiply), তারপর একটা গুণ। `p = 10⁹+7`-এও ~30 ধাপ। brute O(p) (~10⁹)-এর তুলনায় বিশাল লাফ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — `pow` iterative, শুধু গুটিকয় variable। কোনো list/array লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **সরাসরি `/` বা `//` ব্যবহার** — `(a % p) // (b % p)` mod-জগতে ভুল (concept-notes-এর পাল্টা উদাহরণ)। ভাগ মানে inverse দিয়ে গুণ।
- **`b % p == 0` ভুলে যাওয়া** — তখন inverse নেই, ভাগ অসংজ্ঞায়িত; না ধরলে ভুল 0 বা crash।
- **non-prime mod-এ Fermat** — `b^(p−2)` inverse দেয় শুধু p prime হলে। non-prime হলে gcd(b, p)=1 লাগবে + Extended GCD; gcd≠1 হলে inverse-ভিত্তিক একক ভাগফল নেই; সংশ্লিষ্ট congruence-এর শূন্য বা একাধিক সমাধান থাকতে পারে।
- **`a` আগে mod না নেওয়া** — `a` বড় হলে `a %= p` আগে নিলে গুণফল ছোট থাকে; না নিলে অযথা বড়/C++-এ overflow।
- **ভাগের পর যাচাই না করা** — `(result × b) % p == a % p` দিয়ে মিলিয়ে নাও; mod-এর bug একমাত্র এভাবেই ধরা পড়ে।
- **"নিখুঁত ভাগ" আশা করা** — `(a/b) mod p`-এর উত্তর সাধারণ ভাগফলের সমান নাও হতে পারে (যখন b, a-কে নিঃশেষে ভাগ করে না); এটা mod-অর্থে সঠিক, integer ভাগফল নয়।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **034 (nCr mod Prime)** (