Problem link ও উৎস
- **Original source:** Classic exercise (harder variant: CSES — Sum of Divisors)
- **Platform:** CSES —
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Medium
- **Pattern:** exponent formula — σ(n) = ∏ (1 + p + ... + p^e)
- **Basic idea inherited from:** 024 — Number of Divisors
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বের করতে হবে n-এর **সব divisor-এর যোগফল** (sum of divisors, σ(n) দিয়ে লেখা) — মানে 1 থেকে n পর্যন্ত যত সংখ্যা n-কে নিঃশেষে ভাগ করে, তাদের সবার যোগফল।
উদাহরণ: 12-এর divisor 1, 2, 3, 4, 6, 12 — এদের যোগফল 1+2+3+4+6+12 = **28**। তাই σ(12) = 28।
n নিজেও নিজের একটা divisor, তাই যোগফলে n থাকে। (কখনো কখনো "proper divisor sum" মানে n বাদ দিয়ে যোগফল চাওয়া হয় — সেটা পেতে শুধু σ(n) − n; কিন্তু এখানে আমরা n সহ পুরো যোগফল গুনছি।)
### Input ও output {#6-example-input-and-output}
```text
n -> σ(n) factorization / হিসাব
--------------------------------------------------
1 -> 1 শুধু 1
2 -> 3 1 + 2
6 -> 12 1+2+3+6 = (1+2)(1+3)
12 -> 28 (1+2+4)(1+3)
16 -> 31 2^4 -> 1+2+4+8+16
28 -> 56 1+2+4+7+14+28 (perfect number: σ = 2n!)
37 -> 38 prime -> 1 + 37
360 -> 1170 2^3·3^2·5 -> 15·13·6
```
দুটো জিনিস খেয়াল করো: **prime p-এর σ = p + 1** (37 → 38)। আর 28 একটা **perfect number** — তার proper divisor-দের (নিজে বাদে) যোগফল ঠিক নিজে (1+2+4+7+14 = 28), মানে σ(28) = 2×28 = 56।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ফিরে যাই 024-এর সেই পিৎজা-র দোকানে, কিন্তু এবার প্রশ্ন বদলেছে। আগে জিজ্ঞেস করেছিলাম "কত রকম পিৎজা সম্ভব"; এখন জিজ্ঞেস করছি "সব সম্ভাব্য পিৎজার **দাম যোগ করলে** কত"।
ধরো cheese-এর দাম power অনুযায়ী 1, 2, 4 টাকা (0,1,2 চামচ), olive-এর 1, 3 টাকা (0,1 চামচ)। প্রতিটা পিৎজার দাম = তার cheese-দাম × olive-দাম। সব পিৎজার দাম যোগ করতে গেলে দেখা যায় সেটা ঠিক `(1+2+4) × (1+3)` = 7 × 4 = 28 — কারণ বন্ধনী খুললে প্রতিটা পদ এক-একটা পিৎজার দাম।
ঠিক একইভাবে σ(n)-এ প্রতিটা prime-এর "দামের তালিকা" হলো তার power-গুলো (`1, p, p², ...`), আর সব divisor-এর যোগফল = সেই তালিকাগুলোর যোগফলের গুণফল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **024 (Number of Divisors)**-এর উপর দাঁড়িয়ে, আর তার পেছনে 016 (Prime Factorization)। কাঠামো হুবহু এক — factorize করি, প্রতিটা prime-এর exponent পাই, তারপর একটা product বানাই।
একমাত্র পার্থক্য: 024-এ প্রতিটা prime থেকে গুণফলে যোগ হতো `(e + 1)` (পছন্দের সংখ্যা); এখানে যোগ হয় `(1 + p + p² + ... + p^e)` (power-গুলোর যোগফল)। তাই 024 ভালো বুঝে থাকলে এটা প্রায় এক পা — শুধু "গোনা" থেকে "যোগ করা"-য় বদল। আটকালে 024-এ ফিরে যাও।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea 024-এর product formula-রই ভাই, factorization থেকে। `n = p₁^e₁ · p₂^e₂ · ...` হলে:
```text
σ(n) = (1 + p₁ + p₁² + ... + p₁^e₁) · (1 + p₂ + ... + p₂^e₂) · ...
```
মানে প্রতিটা prime-এর জন্য তার সব power-এর যোগফল (`1` থেকে `p^e` পর্যন্ত — একটা geometric series), তারপর সেই যোগফলগুলো সব গুণ করো।
কেন? 024-এ দেখেছি প্রতিটা divisor হলো `p₁^a · p₂^b · ...` রূপের (প্রতিটা prime থেকে একটা power বাছা)। সব divisor যোগ করা মানে এই গুণফলের সব combination যোগ করা — যা বীজগণিতে ঠিক ওই বন্ধনীগুলোর গুণফলের সমান (distributive law খুললে প্রতিটা পদ এক-একটা divisor)। "কয় রকম" এর জায়গায় "সব মিলিয়ে কত" — তাই (e+1) এর বদলে series-যোগফল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
formula মাথায় না এলে, সবচেয়ে সরল — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা দিয়ে n ভাগ করে দেখি, ভাগ গেলে সেটা যোগফলে যোগ করি:
```python
def sum_divisors_brute(n):
total = 0
for d in range(1, n + 1):
if n % d == 0:
total += d # divisor পেলে যোগফলে যোগ
return total
```
একদম সংজ্ঞা: 1..n-এর প্রতিটা d-র জন্য `n % d == 0` হলে divisor, total-এ যোগ করি। সরল, ঠিক উত্তর। (চালাক brute force: √n পর্যন্ত খুঁজে প্রতিবার `d` আর `n // d` দুটোই যোগ — 012/024-এর জোড়ার কৌশল, O(√n)। কিন্তু এখানে factorization-formula পথ দেখব।)
### কোথায় বেশি কাজ হতে পারে {#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)
√n / formula -> n=10^12 হলেও ~10^6 ধাপ (এক লহমায়)
```
মূল সমস্যা 024-এর মতোই: 1..n পুরোটা ঘোরা। divisor-রা √n-এর এপারে জোড়ায় বসে, আর factorization √n-এই শেষ — তাই formula পথে কাজ √n-এ নেমে আসে, n যত বড়ই হোক।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **divisor যোগ করতে প্রতিটা divisor খুঁজতে হয় না; factorization জানলে প্রতিটা prime-এর power-যোগফল বের করে সেগুলো গুণ করলেই σ।**
factorize করার সময়ই প্রতিটা prime-এর exponent গুনি, আর সাথে সাথে তার power-যোগফল (`1 + p + p² + ... + p^e`) হিসাব করে মূল গুণফলে গুণ করি:
```python
def sum_divisors(n):
total = 1
p = 2
while p * p <= n:
if n % p == 0:
power_sum, pw = 1, 1
while n % p == 0:
n //= p
pw *= p
power_sum += pw # 1 + p + p^2 + ...
total *= power_sum
p += 1
if n > 1: # বাকি n নিজেই prime (exponent 1)
total *= (1 + n) # 1 + p
return total
```
মূল চালাকি: power-যোগফলটা loop-এর ভেতরেই গড়ে তুলি — `pw` রাখে current power (p, p², ...), আর `power_sum`-এ যোগ করতে থাকি। আলাদা করে geometric series formula মনে রাখার দরকার নেই, যোগ করতে করতেই হয়ে যায়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **σ হলো 024-এরই formula, শুধু প্রতিটা prime-এর অবদান "(e+1) রকম পছন্দ" থেকে বদলে "তার সব power-এর যোগফল" হয়ে গেছে।**
মূল মোচড়টা distributive law-এ: `(1+p+p²)(1+q)` খুললে প্রতিটা পদ ঠিক এক-একটা divisor — তাই বন্ধনীগুলোর গুণফলই পুরো যোগফল। গোনা (count) আর যোগ (sum) — দুটোই একই "প্রতি prime-এ একটা মান, তারপর গুণ" কাঠামোয় বসে, শুধু ভেতরের মানটা আলাদা। এই "একই কাঠামো, ভেতরটা বদলাও" দৃষ্টিভঙ্গি মাথায় রাখো — divisor product, even-divisor sum ইত্যাদিও এভাবে বেরোয়।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে n = 12-এর divisor হাতে যোগ করি:
```text
12-এর divisor: 1 2 3 4 6 12
যোগফল = 1 + 2 + 3 + 4 + 6 + 12 = 28
```
এবার formula কীভাবে একই 28 দেয় (প্রতি prime-এ power-যোগফল, তারপর গুণ):
```text
12 = 2^2 · 3^1
2-এর power-যোগফল: 1 + 2 + 4 = 7 (2^0 + 2^1 + 2^2)
3-এর power-যোগফল: 1 + 3 = 4 (3^0 + 3^1)
σ(12) = 7 × 4 = 28 ✓
বন্ধনী খুললে প্রতিটা পদ = এক-একটা divisor:
(1+2+4)(1+3) = 1·1 + 2·1 + 4·1 + 1·3 + 2·3 + 4·3
= 1 + 2 + 4 + 3 + 6 + 12 = 28
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো sum_divisors(12) ধীরে চালাই। শুরুতে `total = 1`, `n = 12`:
p = 2-এর ভেতরের while ধাপে ধাপে:
| ভেতরের ধাপ | n হয় | pw (×p) | power_sum (+pw) |
| --- | --- | --- | --- |
| শুরু | 12 | 1 | 1 |
| 1 | 6 | 2 | 1 + 2 = 3 |
| 2 | 3 | 4 | 3 + 4 = 7 |
2 শেষ — `total *= 7` → total = 7। বাইরের loop: p = 3-এ 3·3 > 3 (এখন n = 3), loop শেষ।
Loop-এর পরে `n = 3 > 1`, তাই বাকি 3 একটা prime: `total *= (1 + 3)` → `7 × 4 = 28`।
σ(12) = **28** — section 5-এর হাতে-গোনা 1+2+3+4+6+12-এর সাথে হুবহু মিলল। power_sum 7 = 1+2+4, ঠিক 2-এর সব power-এর যোগ।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def sum_divisors(n):
"""n-এর সব divisor-এর যোগফল σ(n) = ∏ (1 + p + ... + p^e)।"""
if n <= 0:
return 0
total = 1
p = 2
while p * p <= n:
if n % p == 0:
power_sum, pw = 1, 1
while n % p == 0: # 1 + p + p^2 + ... গড়ি
n //= p
pw *= p
power_sum += pw
total *= power_sum
p += 1
if n > 1: # বাকি n নিজেই prime (exponent 1)
total *= (1 + n)
return total
def sum_divisors_brute(n):
"""সংজ্ঞা ধরে: 1..n-এ divisor যোগ — formula verify করতে।"""
return sum(d for d in range(1, n + 1) if n % d == 0)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_divisors(1) == 1
assert sum_divisors(2) == 3
assert sum_divisors(6) == 12 # perfect number: σ = 2n
assert sum_divisors(12) == 28
assert sum_divisors(16) == 31 # 1+2+4+8+16
assert sum_divisors(28) == 56 # perfect number
assert sum_divisors(37) == 38 # prime -> 1 + p
assert sum_divisors(360) == 1170 # 15·13·6
assert sum_divisors(7919) == 7920 # বড় prime -> 1 + p
# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 200):
assert sum_divisors(m) == sum_divisors_brute(m)
print(sum_divisors(12)) # 28
print(sum_divisors(28)) # 56
print(sum_divisors(360)) # 1170
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
total = 1
p = 2
while p * p <= n:
```
`total` শুরুতে 1 (গুণফলের neutral মান)। √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি (factorization-এর মতো)।
```text
if n % p == 0:
power_sum, pw = 1, 1
while n % p == 0:
n //= p
pw *= p
power_sum += pw
```
p যদি n-কে ভাগ করে, তার power-যোগফল গড়ি। `power_sum` শুরুতে 1 (= p⁰), `pw` রাখে current power। প্রতিবার p দিয়ে ভাগ হলে `pw *= p` (পরের power), আর `power_sum += pw` — তাই গড়ে ওঠে `1 + p + p² + ...`।
```text
total *= power_sum
```
এই prime-এর পুরো অবদান (power-যোগফল) মূল গুণফলে গুণ।
```text
if n > 1:
total *= (1 + n)
```
Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর বড় prime factor (exponent 1), তাই তার power-যোগফল `1 + n` দিয়ে গুণ। (যেমন n = 14 = 2×7: loop-এ 2 → total = 3, তারপর 7 এই লাইনে total = 3×8 = 24 = 1+2+7+14 ✓)
`sum_divisors_brute` সংজ্ঞা ধরে যোগ করে; `for m in range(1, 200)` loop দুই version মিলিয়ে formula যাচাই করে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
28
56
1170
সব test pass!
```
প্রথম লাইন: σ(12) = 28 (section 11-এর dry run)। দ্বিতীয়: σ(28) = 56 — 28 perfect number, তাই σ = 2×28। তৃতীয়: σ(360) = 1170 — 360 = 2³·3²·5 → (1+2+4+8)(1+3+9)(1+5) = 15·13·6 = 1170। তার আগে সব `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)** — শুধু `total`, `p`, `power_sum`, `pw`, আর পরিবর্তিত `n` — গুটিকয় variable। divisor-দের কোনো list বানাচ্ছি না, যোগফল চলতে চলতে হিসাব হয়। input ছাড়া আলাদা জায়গা প্রায় শূন্য।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`total` 0 থেকে শুরু করা** — এটা গুণফল, তাই neutral মান **1** থেকে শুরু; 0 থেকে শুরু করলে উত্তর সবসময় 0।
2. **power-যোগফল ভুল গড়া** — `1 + p + ... + p^e` চাই, কিন্তু `pw` শুরু 1 আর `power_sum` শুরু 1 না রাখলে p⁰ পদটা বাদ পড়ে। ক্রম খেয়াল করো: আগে `pw *= p`, তারপর `power_sum += pw`।
3. **শেষের `if n > 1` ভুলে যাওয়া** — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া যোগফলে আসে না, σ কম হয়।
4. **proper divisor sum-এর সাথে গুলিয়ে ফেলা** — এখানে σ-তে n নিজেও আছে; "নিজে বাদে" চাইলে আলাদাভাবে σ(n) − n নিতে হবে।
5. **divisor list বানিয়ে যোগ করা** — শুধু যোগফল চাইলে list বানানোর দরকার নেই; power-যোগফলের গুণফলই যথেষ্ট, memory বাঁচে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Sum of Divisors** (