Problem link ও উৎস
- **Original source:** Classic exercise (modular arithmetic-এর গুণের নিয়ম)
- **Platform:** Classic exercise — সব CP intro আর number theory বই-তে থাকে
- **Topic:** Math-based programming fundamentals → Level 2: Modular Arithmetic
- **Difficulty:** Easy
- **Pattern:** (a*b)%m (modular multiplication)
- **Basic idea inherited from:** 027 — Modular Addition (প্রতি step-এ mod নেওয়ার নিয়ম)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো (বা অনেকগুলো) integer আর একটা `m` দেওয়া। বলতে হবে তাদের **গুণফল mod m** — মানে `(a * b) % m`।
সমস্যাটা যোগের চেয়ে তীব্র: দুটো বড় সংখ্যার গুণফল প্রকাণ্ড হয় (10⁹ × 10⁹ = 10¹⁸)। তাই আমরা চাই — পুরো গুণফল না বানিয়ে, প্রতি step-এ `m`-এর ঘড়িতে নামিয়ে কাজ করতে।
অনেকগুলো সংখ্যার গুণফল (যেমন factorial) হলে এই অভ্যাস ছাড়া উপায় নেই।
### Input ও output {#6-example-input-and-output}
```text
a b m -> (a*b)%m ব্যাখ্যা
-----------------------------------------------------
7 5 12 -> 11 35 % 12 = 11
100 5 12 -> 8 500 % 12 = 8
6 4 7 -> 3 24 % 7 = 3
10**9 10**9 7 -> 1 10^18 % 7 (নিজে মিলাও)
```
list-এর গুণফল (mod):
```text
nums m -> product % m
-----------------------------------------
[2,3,4,5] 7 -> 3 120 % 7 = 3 (= 5! % 7)
[10**9]*5 13 -> ... প্রতি step-এ mod
```
খেয়াল করো `10⁹ × 10⁹ = 10¹⁸` — C++-এ এটা signed 64-bit-এর কিনারায়; বড় হলে overflow।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
আবার **12 ঘণ্টার ঘড়ি**। ধরো প্রতি বৈঠক 7 ঘণ্টা, এমন 5টা বৈঠক পরপর — মোট 7 × 5 = 35 ঘণ্টা পরে কাঁটা কোথায়? `35 % 12 = 11`।
এখন চালাকি: 7 তো ঘড়িতে 7-ই। কিন্তু যদি প্রতি বৈঠক 100 ঘণ্টা হতো? `100 % 12 = 4` — মানে প্রতি বৈঠক ঘড়ির হিসাবে "4 ঘণ্টার সমান"। 5টা বৈঠক = `(4 × 5) % 12 = 20 % 12 = 8`; আর সরাসরি `500 % 12 = 8`। **মিলে গেল!** বড় 500 না বানিয়েও উত্তর পেলাম। এই "আগে ছোট করো, তারপর গুণো" — এটাই modular multiplication।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **027 — Modular Addition** থেকে। 027-এ শিখেছ যোগে প্রতি step-এ mod নিরাপদ; 028 ঠিক একই দর্শন গুণে প্রয়োগ করে।
আসলে গুণ মানে বারবার যোগ — `a × b` মানে `a`-কে `b` বার যোগ। যোগে যদি প্রতি step-এ mod চলে, গুণেও চলবে, এটাই স্বাভাবিক। 027-এর "প্রতি step-এ ছোট করে নাও" idea-টাই এখানে গুণফলে বিস্তৃত।
আর শিকড়ে — 026 (remainder) → 027 (যোগ) → 028 (গুণ); ধাপে ধাপে একই ঘড়ির উপর নতুন operation।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **modular multiplication rule**:
`(a × b) % m = ((a % m) × (b % m)) % m`
গুণের *আগে* দুজনকে আলাদা করে ঘড়ির ঘরে নামিয়ে নিলেও শেষ উত্তর একই।
কেন? `a = q₁m + r₁`, `b = q₂m + r₂` লিখলে:
`a × b = q₁q₂m² + q₁m·r₂ + r₁·q₂m + r₁r₂`
প্রথম তিনটে term-এ `m` আছে — ঘড়িতে পুরো পুরো চক্কর, কাঁটার অবস্থানে প্রভাব নেই। কাঁটা কোথায় থামবে তা ঠিক করে শুধু শেষ term `r₁ × r₂`। তাই `(a×b) % m = (r₁ × r₂) % m`।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল: পুরো গুণফল বানিয়ে শেষে একবার mod।
```python
def mul_mod_brute(a, b, m):
return (a * b) % m # আগে পুরো গুণফল, তারপর mod
def product_mod_brute(nums, m):
p = 1
for x in nums:
p *= x # পুরো গুণফল জমাতে থাকি
return p % m # শেষে একবার mod
```
Python-এ ঠিক উত্তর দেয়। কিন্তু এখানেই বিপদের বীজ — গুণফল লাফিয়ে লাফিয়ে বাড়ে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
গুণে সংখ্যা যোগের চেয়ে **অনেক দ্রুত** বাড়ে:
1. **C++/Java-তে overflow:** `10⁹ × 10⁹ = 10¹⁸` 64-bit-এর সীমার কাছে; আর কয়েকটা গুণেই সীমা ছাড়িয়ে wrap → garbage।
2. **Python-এ slowness:** `product_mod_brute`-এ মাঝের গুণফল লক্ষ লক্ষ digit-এর হয়ে যায় (যেমন 100! বা বড়), প্রতিটা গুণ ক্রমশ ধীর; পুরো হিসাব সেকেন্ড-মিনিটে গড়ায়।
```text
factorial(100000) % MOD:
brute: মাঝের গুণফল ~456574 digit, প্রতিটা গুণ ভয়াবহ ধীর
smart: প্রতি গুণের পরেই % MOD -> সংখ্যা কখনো MOD² ছাড়ায় না, ঝটপট
```
মূল শিক্ষা: গুণফলকে বড় হওয়ার সুযোগই দিও না।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
modular multiplication rule কাজে লাগাই — প্রতি গুণের পরেই mod:
```python
def mul_mod(a, b, m):
return ((a % m) * (b % m)) % m
```
list-এর জন্য প্রতি step-এ mod নিয়ে জমাও:
```python
def product_mod(nums, m):
p = 1
for x in nums:
p = p * x % m # প্রতি গুণের পরেই ঘড়িতে নামাও
return p
```
এখন মাঝের `p` কখনো `m²`-এর বেশি বড় হয় না — ছোট, দ্রুত, overflow-মুক্ত। factorial-mod এই কাঠামোতেই লেখা হয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!": **গুণফলকে বড় হতে দিও না — প্রতিটা গুণের পরপরই `% m` নাও।** গুণে বৃদ্ধি যোগের চেয়ে দ্রুত, তাই এই অভ্যাসটা আরও জরুরি।
আরেকটা সূক্ষ্ম tweak: `p = p * x % m`-এ Python operator precedence-এ `*` আগে চলে, তারপর `%` — মানে এটা `(p * x) % m`, ঠিক যা চাই। কিন্তু পরিষ্কার থাকতে চাইলে bracket দিয়ে `p = (p * x) % m` লেখো; দুটো একই।
### ছবিতে বোঝা {#5-visual-explanation}
`m = 12` ধরে, গুণের আগে-পরে mod একই ফল দেয়:
```text
(100 × 5) % 12 দুই রাস্তায়:
রাস্তা A (সরাসরি): 100 × 5 = 500 -> 500 % 12 = 8
রাস্তা B (প্রতি step):
100 % 12 = 4
5 % 12 = 5
(4 × 5) % 12 = 20 % 12 = 8
^ একই! কিন্তু সংখ্যা কখনো 20 ছাড়াল না
```
অনেকগুলো গুণে (factorial-এর মতো) সংখ্যা ছোট থাকে দেখো — `5! % 7`:
```text
result শুরুতে 1, প্রতি step-এ × i তারপর % 7:
1 ──×2──> 2 %7=2 ──×3──> 6 %7=6 ──×4──> 24 %7=3 ──×5──> 15 %7=1
^
result কখনো 6×5=30-এর বেশি গেল না, যদিও 5! = 120
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [2, 3, 4, 5]`, `m = 7` (মানে 4! × ... আসলে 2×3×4×5 = 120 = 5!) — প্রতি step-এ mod:
| step | x | p (আগে) | p * x | (p * x) % 7 |
| --- | --- | --- | --- | --- |
| শুরু | — | 1 | — | 1 |
| 1 | 2 | 1 | 2 | 2 % 7 = 2 |
| 2 | 3 | 2 | 6 | 6 % 7 = 6 |
| 3 | 4 | 6 | 24 | 24 % 7 = 3 |
| 4 | 5 | 3 | 15 | 15 % 7 = 1 |
উত্তর **1**। Check সরাসরি: 2×3×4×5 = 120, `120 % 7 = 1` ✓ (120 = 7×17 + 1)। লক্ষ করো `p` কখনো 24-এর বেশি গেল না, যদিও পুরো গুণফল 120।
single গুণ dry run `(100 × 5) % 12`:
```text
100 % 12 = 4, 5 % 12 = 5
(4 × 5) % 12 = 20 % 12 = 8
Check: 500 % 12 = 8 ✓
```
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mul_mod(a, b, m):
"""(a * b) % m — প্রতি অপারেন্ড আগে ঘড়িতে নামিয়ে।"""
return ((a % m) * (b % m)) % m
def product_mod(nums, m):
"""list-এর সব সংখ্যার গুণফল mod m — প্রতি step-এ mod।"""
p = 1
for x in nums:
p = (p * x) % m
return p
def factorial_mod(n, m):
"""n! % m — modular multiplication-এর সরাসরি প্রয়োগ।"""
p = 1
for i in range(2, n + 1):
p = (p * i) % m
return p
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert mul_mod(7, 5, 12) == 11 # 35 % 12
assert mul_mod(100, 5, 12) == 8 # 500 % 12
assert mul_mod(6, 4, 7) == 3 # 24 % 7
# brute (সরাসরি গুণ) এর সাথে মিলিয়ে দেখা:
assert mul_mod(10**9, 10**9, 7) == (10**9 * 10**9) % 7
assert product_mod([2, 3, 4, 5], 7) == 1 # 120 % 7
assert product_mod([2, 3, 4, 5], 7) == (2 * 3 * 4 * 5) % 7
assert factorial_mod(5, 7) == 1 # 120 % 7 = 1
import math
assert factorial_mod(10, 1000000007) == math.factorial(10) % 1000000007
assert factorial_mod(20, 13) == math.factorial(20) % 13
print(mul_mod(7, 5, 12)) # 11
print(product_mod([2, 3, 4, 5], 7)) # 1
print(factorial_mod(5, 7)) # 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def mul_mod(a, b, m):
return ((a % m) * (b % m)) % m
```
দুজনকে আগে আলাদা করে ঘড়িতে নামাই, গুণ করি, আবার `% m`। তাই মাঝের গুণফল কখনো `m²`-এর বেশি বড় হয় না — overflow-নিরাপদ।
```text
def product_mod(nums, m):
p = 1
for x in nums:
p = (p * x) % m
return p
```
`p` শুরু 1 (গুণের identity)। প্রতিটা সংখ্যা গুণ করি, কিন্তু **প্রতি step-এই** `% m`। তাই `p` ছোট থাকে।
```text
def factorial_mod(n, m):
p = 1
for i in range(2, n + 1):
p = (p * i) % m
return p
```
2 থেকে n পর্যন্ত গুণ — এটাই n! কিন্তু প্রতি step-এ mod নেওয়া। nCr mod p-এর factorial precompute এই কাঠামোরই বড় রূপ।
`assert ... == math.factorial(...) % ...` লাইনগুলো Python-এর সত্যিকার factorial-এর সাথে মিলিয়ে দেখছে — এটাই নিশ্চিত করে আমাদের mod-হিসাবে ভুল নেই। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
11
1
1
সব test pass!
```
প্রথম লাইন `mul_mod(7, 5, 12)` → 11 (35 mod 12)। দ্বিতীয় `product_mod([2,3,4,5], 7)` → 1 (120 mod 7)। তৃতীয় `factorial_mod(5, 7)` → 1 (5! = 120, mod 7 = 1)। আগের সব `assert` (`math.factorial`-এর সাথে মিল সহ) চুপচাপ pass — তারপর `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
- `mul_mod`: **O(1)** — গুটিকয় mod আর একটা গুণ।
- `product_mod`, `factorial_mod`: **O(n)** — `n` টা সংখ্যার উপর একবার করে loop, প্রতিবার O(1) কাজ।
brute force-এর সাথে Big-O একই, কিন্তু এখানে মাঝের সংখ্যা ছোট থাকায় প্রতিটা গুণ সস্তা (বড় সংখ্যার গুণ Python-এ ধীর) আর C++-এ overflow নেই।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — input ছাড়া শুধু একটা `p` variable। বাড়তি list/array লাগছে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **শেষে একবারে mod নেওয়া** — `(a * b * c) % m` Python-এ ঠিক, কিন্তু মাঝের সংখ্যা বিশাল হয়ে slow; C++/Java-তে overflow-এ ভুল উত্তর। অভ্যাস: **প্রতি গুণের পরেই `% m`**।
- **`10⁹ × 10⁹` C++-এ সরাসরি গুণ** — 10¹⁸ signed 64-bit-এর কিনারায়; কয়েক গুণেই overflow। আগে mod নিয়ে তারপর গুণ নিরাপদ।
- **`p` শুরুতে 0 দেওয়া** — গুণে identity হলো 1, 0 নয়; `p = 0` দিলে সব গুণফল 0।
- **mod 1 ভুলে যাওয়া** — সব কিছু mod 1 = 0; factorial-ও 0।
- **operand আগে mod না নেওয়া** — `a` নিজেই m-এর চেয়ে বড় হলে `(a % m)` আগে নিলে গুণফল আরও ছোট থাকে; নাহলে অযথা বড় সংখ্যার গুণ।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Exponentiation** (