Problem link ও উৎস
- **Original source:** CSES Problem Set — Counting Divisors
- **Platform:** CSES —
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Medium
- **Pattern:** exponent formula — d(n) = ∏(eᵢ + 1)
- **Basic idea inherited from:** 016 — Prime Factorization
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বের করতে হবে n-এর **মোট কয়টা divisor** (গুণনীয়ক) আছে — মানে 1 থেকে n পর্যন্ত (n সহ) কয়টা সংখ্যা n-কে নিঃশেষে ভাগ করে।
উদাহরণ: 12-এর divisor হলো 1, 2, 3, 4, 6, 12 — মোট **6**টা। তাই d(12) = 6।
কয়েকটা সীমা: প্রতিটা সংখ্যার অন্তত 2টা divisor (1 আর সে নিজে), শুধু 1-এর একটাই (নিজে)। আর prime-এর ঠিক 2টা।
### Input ও output {#6-example-input-and-output}
```text
n -> d(n) factorization
-----------------------------------------
1 -> 1 (খালি; কোনো prime নেই)
2 -> 2 2^1 -> (1+1)
6 -> 4 2·3 -> (1+1)(1+1)
12 -> 6 2^2·3 -> (2+1)(1+1)
16 -> 5 2^4 -> (4+1)
36 -> 9 2^2·3^2 -> (2+1)(2+1)
37 -> 2 prime -> (1+1)
360 -> 24 2^3·3^2·5 -> 4·3·2
```
দুটো জিনিস খেয়াল করো: **prime-এর ঠিক 2টা divisor** (37 → 2)। আর **perfect power-এর divisor বিজোড় হয়** — 36 (= 6²) → 9টা, কারণ একটা divisor (এখানে 6) তার জোড়া নিজেই; বাকিরা জোড়ায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা পিৎজা অর্ডার করছ, আর তিন রকম topping আছে যেগুলো তুমি 0 থেকে কিছু সর্বোচ্চ পরিমাণ পর্যন্ত নিতে পারো — ধরো cheese 0-3 চামচ, olive 0-2 চামচ, mushroom 0-1 চামচ। কত রকম আলাদা পিৎজা বানানো সম্ভব?
cheese-এ 4 রকম পছন্দ (0,1,2,3), olive-এ 3 রকম (0,1,2), mushroom-এ 2 রকম (0,1)। প্রতিটা স্বাধীন, তাই মোট = 4 × 3 × 2 = 24 রকম পিৎজা।
ঠিক এভাবেই divisor বানানো: প্রতিটা prime হলো এক-একটা topping, exponent হলো তার সর্বোচ্চ পরিমাণ, আর প্রতিটা divisor হলো এক-একটা আলাদা পিৎজা। `n = 2³·3²·5¹`-এর divisor সংখ্যা = 4 × 3 × 2 = 24।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **016 (Prime Factorization)**-এর উপর দাঁড়িয়ে। divisor গোনার formula চালাতে আগে n-এর প্রতিটা prime আর তার exponent জানা চাই — সেটাই 016-এর কাজ। আমরা ছোট prime দিয়ে n-কে খোসা ছাড়িয়ে প্রতিটা prime কতবার এল (exponent) গুনি, তারপর `(e+1)` গুলো গুণ করি।
মূল পার্থক্য: 016 দেয় factorization (কোন prime কয়বার); 024 সেই exponent থেকে এক ধাপে divisor সংখ্যা বের করে। তাই factorization-এ আটকালে এক ধাপ পিছিয়ে 016-এ যাও।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea factorization থেকে আসা একটা **product formula**। n-কে prime-এর power-এ লিখলে `n = p₁^e₁ · p₂^e₂ · ...`, তাহলে:
```text
d(n) = (e₁ + 1) · (e₂ + 1) · ...
```
মানে প্রতিটা prime-এর exponent-এর সাথে 1 যোগ করে সব গুণ করো।
কেন? একটা divisor বানাতে হলে প্রতিটা prime থেকে "কয়টা power নেব" বেছে নিতে হয়। p₁ থেকে নিতে পারি 0, 1, 2, ..., e₁ — মোট **(e₁ + 1) রকম** পছন্দ। প্রতিটা prime-এর পছন্দ স্বাধীন (independent), তাই মোট divisor = সব পছন্দের গুণফল। এটা আসলে Level 3-এর multiplication principle-এর আগাম রূপ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
factorization-formula মাথায় না এলে, সবচেয়ে সরল — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দিয়ে n ভাগ করে দেখি, ভাগ গেলে divisor, গুনি:
```python
def count_divisors_brute(n):
count = 0
for d in range(1, n + 1):
if n % d == 0:
count += 1
return count
```
এটা একদম সংজ্ঞা: 1..n-এর প্রতিটা d-র জন্য `n % d == 0` হলে divisor, count বাড়াই। সরল, ঠিক উত্তর। (একটু চালাক brute force: √n পর্যন্ত খুঁজে জোড়াসুদ্ধ গোনা — 012-এর কৌশল, O(√n)। কিন্তু এখানে আমরা formula-ভিত্তিক পথ দেখব, যেটা factorization জানা থাকলে আরও তথ্যপূর্ণ।)
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই সরল loop ঠিক `n` বার ঘোরে। ছোট n-এ ঠিক আছে, কিন্তু n বিশাল হলে অসম্ভব:
```text
n = 10^6 -> 10^6 বার (ঠিক আছে)
n = 10^9 -> 10^9 বার (ধীর)
n = 10^12 -> 10^12 বার (অসম্ভব — TLE; যেমন CSES-এ n বড়)
√n / formula -> n=10^12 হলেও ~10^6 ধাপ (এক লহমায়)
```
মূল সমস্যা: 1..n পুরোটা ঘোরা। অথচ divisor-রা √n-এর এপারে জোড়ায় বসে (012), আর factorization-ও √n-এই শেষ। তাই formula পথে কাজ √n-এ নেমে আসে — n যত বড়ই হোক।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **divisor গুনতে প্রতিটা সম্ভাব্য divisor খুঁজতে হয় না; n-এর factorization জানলে exponent থেকে এক গুণফলেই উত্তর।**
আমরা factorize করার সময়ই (016-এর মতো) প্রতিটা prime-এর exponent গুনি, আর সাথে সাথে `(e + 1)` গুণ করে চলি:
```python
def count_divisors(n):
count = 1
p = 2
while p * p <= n:
if n % p == 0:
e = 0
while n % p == 0: # এই prime কতবার? -> exponent
n //= p
e += 1
count *= (e + 1) # এই prime থেকে (e+1) রকম পছন্দ
p += 1
if n > 1: # বাকি n নিজেই একটা prime (exponent 1)
count *= 2 # (1 + 1)
return count
```
মূল চালাকি: factorization আর গোনা একসাথে — আলাদা করে divisor list বানানোর দরকারই নেই। আর শেষের `if n > 1` (exponent 1, তাই × 2) — n-এর বড় prime factor ধরার জন্য।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **প্রতিটা divisor আসলে "প্রতিটা prime থেকে কত power নেব"-এর একটা পছন্দ; তাই divisor *গোনা* = পছন্দ *গোনা* = (e+1) গুলোর গুণফল।**
মূল মোচড়টা হলো divisor-দের একটা একটা করে না খুঁজে, তাদের "গঠনের নিয়ম" দেখা। `n = p₁^e₁ · ...`-এর প্রতিটা divisor `p₁^a · p₂^b · ...` রূপের, যেখানে `0 ≤ a ≤ e₁`, ইত্যাদি। প্রতিটা exponent-এর জন্য (e+1) রকম স্বাধীন পছন্দ — তাই গুণ। এই "independent choice → গুণ" নিয়মটা মাথায় গাঁথো; Level 3-এ পুরো combinatorics এর উপর দাঁড়াবে।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে n = 12-এর সব divisor হাতে লিখি — জোড়ায় জোড়ায় আসে:
```text
12-এর divisor (জোড়ায়):
1 × 12 2 × 6 3 × 4
-> 1, 2, 3, 4, 6, 12 -> মোট 6টা
```
এবার formula কীভাবে একই 6 দেয় (exponent থেকে choice গোনা):
```text
12 = 2^2 · 3^1
2-এর power বাছো: 2^0, 2^1, 2^2 -> 3 রকম (= 2+1)
3-এর power বাছো: 3^0, 3^1 -> 2 রকম (= 1+1)
d(12) = 3 × 2 = 6 ✓
প্রতিটা combination একটা divisor:
2^0·3^0=1 2^1·3^0=2 2^2·3^0=4
2^0·3^1=3 2^1·3^1=6 2^2·3^1=12
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো count_divisors(12) ধীরে চালাই। শুরুতে `count = 1`, `n = 12`:
| p | n % p == 0? | ভেতরের while: n হয়, e হয় | count বদল | count |
| --- | --- | --- | --- | --- |
| 2 | হ্যাঁ | 12→6→3, e = 2 | 1 × (2+1) | 3 |
| 3 | 3·3 > 3, loop শেষ | — | — | 3 |
Loop-এর পরে `n = 3 > 1`, তাই বাকি 3 একটা prime (exponent 1): `count *= 2` → `3 × 2 = 6`।
d(12) = **6** — section 5-এর হাতে-গোনা 1,2,3,4,6,12-এর সাথে হুবহু মিলল। লক্ষ করো: 2-এর exponent 2 → (2+1) = 3; 3-এর exponent 1 → (1+1) = 2; গুণফল 6।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def count_divisors(n):
"""n-এর মোট divisor সংখ্যা — exponent formula d(n) = ∏(eᵢ + 1)।"""
if n <= 0:
return 0
count = 1
p = 2
while p * p <= n:
if n % p == 0:
e = 0
while n % p == 0: # exponent গোনা
n //= p
e += 1
count *= (e + 1)
p += 1
if n > 1: # বাকি n নিজেই prime (exponent 1)
count *= 2
return count
def count_divisors_brute(n):
"""সংজ্ঞা ধরে: 1..n-এ ভাগ গোনা — formula verify করতে।"""
return sum(1 for d in range(1, n + 1) if n % d == 0)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_divisors(1) == 1
assert count_divisors(2) == 2
assert count_divisors(6) == 4
assert count_divisors(12) == 6
assert count_divisors(16) == 5 # 2^4 -> 5
assert count_divisors(36) == 9 # perfect square -> বিজোড়
assert count_divisors(37) == 2 # prime
assert count_divisors(360) == 24 # 2^3·3^2·5
assert count_divisors(7919) == 2 # বড় prime
# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 200):
assert count_divisors(m) == count_divisors_brute(m)
print(count_divisors(12)) # 6
print(count_divisors(36)) # 9
print(count_divisors(360)) # 24
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
count = 1
p = 2
while p * p <= n:
```
`count` শুরুতে 1 (গুণফলের neutral মান)। তারপর √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি (factorization-এর মতো — কোনো prime factor √n-এর এপারে অবশ্যই থাকে, বড়জোর একটা ছাড়া)।
```text
if n % p == 0:
e = 0
while n % p == 0:
n //= p
e += 1
```
p যদি n-কে ভাগ করে, ভেতরের while দিয়ে গুনি p কতবার যায় — সেটাই exponent `e`। সাথে সাথে n থেকে সব p সরিয়ে ফেলি।
```text
count *= (e + 1)
```
এটাই formula-র হৃদয়: এই prime থেকে (e+1) রকম পছন্দ, তাই count-কে (e+1) দিয়ে গুণ।
```text
if n > 1:
count *= 2
```
Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর বড় prime factor (exponent 1), তাই (1+1) = 2 দিয়ে গুণ। (যেমন n = 14 = 2×7: loop-এ 2 ধরা পড়ে count = 2, তারপর n = 7 এই লাইনে count = 4।)
`count_divisors_brute` সংজ্ঞা ধরে গোনে; `for m in range(1, 200)` loop দুই version মিলিয়ে formula-র correctness যাচাই করে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
6
9
24
সব test pass!
```
প্রথম লাইন: d(12) = 6 (section 11-এর dry run)। দ্বিতীয়: d(36) = 9 — 36 = 2²·3² → (2+1)(2+1) = 9, perfect square তাই বিজোড়। তৃতীয়: d(360) = 24 — 360 = 2³·3²·5 → 4·3·2 = 24। তার আগে সব `assert`, এমনকি 1..199 জুড়ে formula-vs-brute মিল — সব চুপচাপ pass, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — মূল loop p চলে 2 থেকে √n পর্যন্ত (factorization-এর খরচ); ভেতরের while-গুলো মিলিয়েও মোট কাজ O(√n)-এই থাকে। তাই n = 10¹² হলেও √n = 10⁶ — এক লহমায় শেষ। সরল brute force-এর O(n)-এর তুলনায় বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `count`, `p`, `e`, আর পরিবর্তিত `n` — গুটিকয় variable। divisor-দের কোনো list বানাচ্ছি না, শুধু গুনছি। input ছাড়া আলাদা জায়গা প্রায় শূন্য।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`count` 0 থেকে শুরু করা** — এটা গুণফল, তাই neutral মান **1** থেকে শুরু; 0 থেকে শুরু করলে উত্তর সবসময় 0।
2. **`e` না `(e + 1)` দিয়ে গুণ** — মনে রেখো প্রতিটা prime-এ পছন্দ `0..e` মানে (e+1) রকম, শুধু e নয়। 12-এ 2-এর জন্য 3 (0,1,2), 2 নয়।
3. **শেষের `if n > 1` ভুলে যাওয়া** — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া গোনা হয় না, উত্তর কম আসে।
4. **divisor list বানিয়ে memory নষ্ট** — শুধু সংখ্যা চাইলে list বানানোর দরকার নেই; exponent গুণফলই যথেষ্ট।
5. **n = 1 ভুলে যাওয়া** — 1-এর কোনো prime factor নেই, loop চলে না, count থাকে 1 — যা ঠিক (1-এর একটাই divisor)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Divisors** (