Problem link ও উৎস
- **Original source:** Wikipedia — Möbius function
- **Platform:** Wikipedia —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Hard
- **Pattern:** IE encoding (inclusion-exclusion encoding)
- **Basic idea inherited from:** 044 (Inclusion-Exclusion), 128 (Euler Totient Advanced)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বের করতে হবে **μ(n)** (Mobius function), যার মান শুধু তিনটার একটা — `1`, `−1`, বা `0` — নিয়ম এই:
```
μ(n) = 1 যদি n = 1
μ(n) = (−1)^k যদি n হয় k-টা ভিন্ন prime-এর গুণফল (square-free, কোনো prime² ভাগ করে না)
μ(n) = 0 যদি কোনো prime-এর বর্গ (p²) n-কে ভাগ করে
```
উদাহরণ: μ(6) = μ(2·3) = (−1)² = 1; μ(30) = μ(2·3·5) = (−1)³ = −1; μ(12) = 0 (কারণ 4 = 2² ভাগ করে)।
পাশাপাশি প্রায়ই দরকার হয় `1` থেকে `N`-এর সব μ একসাথে — তখন একটা **sieve** দিয়ে O(N log log N)-এ পুরো array বানানো যায়। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু μ সংখ্যাতত্ত্বের সবচেয়ে কেতাদুরস্ত খেলনাগুলোর একটা।
### Input ও output {#6-example-input-and-output}
```text
input n -> μ(n) কেন
----------------------------------------------------------------
1 -> 1 convention
2 -> -1 1টা prime
6 -> 1 2টা prime (2·3)
30 -> -1 3টা prime (2·3·5)
4 -> 0 2² ভাগ করে
12 -> 0 2² ভাগ করে
35 -> 1 5·7, 2টা prime
210 -> 1 2·3·5·7, 4টা prime -> (−1)⁴
17 -> -1 prime
```
খেয়াল করো: **square-free** (কোনো বর্গ ভাগ করে না) হলে μ = (−1)^(distinct prime সংখ্যা); নাহলে 0। আর μ(1) = 1 (convention, কারণ 1-এর কোনো prime নেই, (−1)⁰ = 1)। 210 = 2·3·5·7 — চারটা prime, তাই (−1)⁴ = +1।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা ঘরে ঢুকছ যেখানে সুইচ আছে, আর প্রতিটা distinct prime একটা করে সুইচ টেপে — প্রতিটা চাপ আলো **on→off→on** উল্টে দেয় (টগল)।
- কোনো prime নেই (n = 1) → আলো জ্বলছে → μ = +1
- 1টা prime → একবার টগল → অন্ধকার → μ = −1
- 2টা prime → দুবার টগল → আবার আলো → μ = +1
- 3টা prime → আবার অন্ধকার → μ = −1
আর একটা বিশেষ নিয়ম: যদি কোনো prime **দুবার** আসে (মানে p² ভাগ করে), সুইচটা পুড়ে যায় — পুরো ঘর চিরতরে অন্ধকার, μ = **0**। তাই μ দুই জিনিস বলে দেয়: (ক) আলো জ্বলছে না নিভছে (distinct prime জোড় না বিজোড়), আর (খ) সুইচ পুড়ে গেছে কি না (square আছে কি না)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
দুটো শিকড়:
- **044 (Inclusion-Exclusion)** — μ আসলে IE-র sign-choreography। "ঠিক gcd = 1 কতগুলো জোড়া" বা "square-free কতগুলো" গুনতে IE-র যে যোগ-বিয়োগ লাগে, μ সেগুলো এক sum-এ গুছিয়ে দেয়: `∑ μ(d) · (d-এর গুণিতক গোনা)`।
- **128 (Euler Totient Advanced)** — μ-ও φ-এর মতো multiplicative, একই prime-factorization-চিন্তায় বসে। φ "কতগুলো coprime" গোনে; μ "কীভাবে coprime-গোনাকে এক সূত্রে আনা যায়" তার চাবি (Mobius inversion)।
তাই README-র recommended order-এ 128 → 129 পরপর — দুটোই multiplicative function-এর জগৎ।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **inclusion-exclusion-এর sign-গুলোকে একটা function-এ encode করা**। 044-তে দেখেছিলে "2 বা 3 বা 5 দিয়ে ভাগ যায় এমন কতগুলো" গুনতে যোগ-বিয়োগের নাচ: একটা set যোগ, জোড়া-overlap বিয়োগ, তিন-overlap আবার যোগ... । μ ঠিক সেই sign-প্যাটার্নটাই ধরে রাখে:
- 1টা prime → sign −1 (বিয়োগ)
- 2টা prime → sign +1 (যোগ)
- 3টা prime → sign −1
- কোনো prime বর্গ থাকলে → 0 (এই পদ একদম বাদ)
আর μ **multiplicative** (128-এর φ-এর মতো): `gcd(a, b) = 1` হলে `μ(a·b) = μ(a)·μ(b)`। এই level CP-leaning হলেও মূল সুর সরল — μ হলো "কয়টা distinct prime, জোড় না বিজোড়, আর কোনো বর্গ আছে কি না" — এই তিন প্রশ্নের একলাইন উত্তর।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি সংজ্ঞা থেকে — **একটা সংখ্যাকে prime-এ factorize করে দেখি কোনো prime দুবার আসে কি না, আর কয়টা distinct prime**:
```python
def mobius_one(n):
if n == 1:
return 1
cnt = 0 # distinct prime গোনা
p = 2
while p * p <= n:
if n % p == 0:
n //= p
cnt += 1
if n % p == 0: # p আবার ভাগ করল -> p² আছে
return 0
p += 1
if n > 1: # অবশিষ্ট বড় prime
cnt += 1
return -1 if cnt % 2 else 1
```
একটা সংখ্যার জন্য এটা নিখুঁত — trial division করে square ধরা পড়লেই 0, নাহলে distinct prime গুনে ±1। শুরুর জন্য পরিষ্কার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
একটা সংখ্যার জন্য এটা O(√n) — ঠিক আছে। সমস্যা হয় যখন **1 থেকে N-এর সব μ** চাই (CP-তে এটাই বেশি দরকার): প্রতিটা সংখ্যায় আলাদা factorization মানে মোট O(N√N)।
```text
একটা μ(n): O(√n) — ঠিক আছে
1..N সব μ, একে একে: N × O(√N) = O(N^1.5) — N=10⁶ হলে 10⁹ ধাপ, ধীর
sieve দিয়ে সব μ: O(N log log N) — N=10⁶ মুহূর্তে
```
বহুবার μ লাগলে প্রতিবার factorize করা অপচয়। sieve একবারে পুরো array বানিয়ে দেয়, তারপর প্রতিটা lookup O(1)।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **sieve দিয়ে একবারে 1 থেকে N-এর সব μ বানিয়ে ফেলা।** Eratosthenes-এর ছাঁকনির মতো, কিন্তু প্রতিটা prime দিয়ে কাটার সময় sign উল্টাই আর square ধরা পড়লে 0 বসাই:
```text
1. mu[i] = 1 সবার জন্য শুরু
2. প্রতিটা prime p-এর জন্য (যেটা এখনো mark হয়নি):
p-এর প্রতিটা গুণিতক j-এর mu[j]-এর sign উল্টাও (× −1) [একটা prime যোগ হলো]
p²-এর প্রতিটা গুণিতক j-এর mu[j] = 0 বসাও [square আছে]
```
এভাবে প্রতিটা সংখ্যা তার distinct prime অনুযায়ী ±1 পায়, আর কোনো square থাকলে 0। একটামাত্র সংখ্যা চাইলে অবশ্য section 7-এর factorization (O(√n)) যথেষ্ট — দুটো পথই আমরা রাখব আর মিলিয়ে দেখব।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **μ আসলে inclusion-exclusion-এর sign — তাই "জোড় না বিজোড় distinct prime" আর "square আছে কি না", এই দুটো প্রশ্নের উত্তরই পুরো μ।**
brute force প্রতিবার পুরো factorization করছিল; tweak হলো — sieve-এ প্রতিটা prime একবারই তার গুণিতকদের sign উল্টে দিক, আর p²-এর গুণিতকদের 0 করে দিক। তখন O(√n) প্রতি-সংখ্যা থেকে O(log log N) amortized প্রতি-সংখ্যায় নেমে আসে। আর বড় ছবি: μ পেলে IE-র গোটা যোগ-বিয়োগ এক sum `∑ μ(d)·f(d)`-এ গুটিয়ে যায়।
### ছবিতে বোঝা {#5-visual-explanation}
μ-এর table, 1 থেকে 12 — সাথে কারণ:
```text
n | factorization | distinct primes (k) | square আছে? | μ(n)
---+---------------+---------------------+-------------+------
1 | — | 0 | না | +1 (convention)
2 | 2 | 1 | না | −1 (−1)¹
3 | 3 | 1 | না | −1
4 | 2² | — | হ্যাঁ (2²) | 0
5 | 5 | 1 | না | −1
6 | 2·3 | 2 | না | +1 (−1)²
7 | 7 | 1 | না | −1
8 | 2³ | — | হ্যাঁ (2²) | 0
9 | 3² | — | হ্যাঁ (3²) | 0
10 | 2·5 | 2 | না | +1
11 | 11 | 1 | না | −1
12 | 2²·3 | — | হ্যাঁ (2²) | 0
μ : 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0
```
লক্ষ করো — যেই কোনো বর্গ (4, 8, 9, 12) ভাগ করে, μ সঙ্গে সঙ্গে 0; বাকিদের জন্য শুধু distinct prime গুনে জোড়-বিজোড় দিয়ে ±1।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
sieve দিয়ে `mu[1..6]` বানানো — শুরুতে সবার mu = 1, is_prime ধরে এগোই:
| ধাপ | কী হলো | mu array (index 1..6) |
| --- | --- | --- |
| শুরু | সব mu = 1 | [_, 1, 1, 1, 1, 1, 1] |
| p = 2 (prime) | 2-এর গুণিতক (2,4,6) sign উল্টাও | [_, 1, −1, 1, −1, 1, −1] |
| p = 2 | 4-এর গুণিতক (4) → mu = 0 | [_, 1, −1, 1, 0, 1, −1] |
| p = 3 (prime) | 3-এর গুণিতক (3,6) sign উল্টাও | [_, 1, −1, −1, 0, 1, 1] |
| p = 3 | 9-এর গুণিতক (>6, নেই) | [_, 1, −1, −1, 0, 1, 1] |
| p = 5 (prime) | 5-এর গুণিতক (5) sign উল্টাও | [_, 1, −1, −1, 0, −1, 1] |
চূড়ান্ত mu[1..6] = [1, −1, −1, 0, −1, 1]। মিলিয়ে দেখো section 5-এর table-এর সাথে — হুবহু। লক্ষ করো 6 প্রথমে 2-এর হাতে −1 হলো, তারপর 3-এর হাতে আবার উল্টে +1 (দুটো distinct prime, তাই +1)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def mobius_one(n):
"""একটা সংখ্যার μ(n) — trial division, O(√n)।"""
if n == 1:
return 1
cnt = 0
p = 2
while p * p <= n:
if n % p == 0:
n //= p
cnt += 1
if n % p == 0: # p আবার ভাগ করল -> square
return 0
p += 1
if n > 1:
cnt += 1 # অবশিষ্ট বড় prime
return -1 if cnt % 2 else 1
def mobius_sieve(N):
"""1..N সব μ একসাথে — O(N log log N)। mu[0] অব্যবহৃত।"""
mu = [1] * (N + 1)
is_comp = [False] * (N + 1)
for p in range(2, N + 1):
if not is_comp[p]: # p prime
for j in range(p, N + 1, p):
if j > p:
is_comp[j] = True
mu[j] *= -1 # একটা prime যোগ -> sign উল্টাও
p2 = p * p
for j in range(p2, N + 1, p2):
mu[j] = 0 # p² ভাগ করে -> 0
return mu
# --- ছোট test গুলো (সব pass করা উচিত) ---
EXPECTED = [None, 1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0] # μ(1..12)
# এক-সংখ্যা version যাচাই
for n in range(1, 13):
assert mobius_one(n) == EXPECTED[n], f"mobius_one({n}) ভুল"
# কিছু বড় মান
assert mobius_one(30) == -1 # 2·3·5
assert mobius_one(210) == 1 # 2·3·5·7
assert mobius_one(35) == 1 # 5·7
assert mobius_one(49) == 0 # 7²
# sieve version — এক-সংখ্যা version-এর সাথে 1..500 মেলাও
mu = mobius_sieve(500)
for n in range(1, 501):
assert mu[n] == mobius_one(n), f"sieve বনাম one অমিল at {n}"
# multiplicative property: gcd=1 হলে μ(ab) = μ(a)μ(b)
from math import gcd
for a in range(1, 30):
for b in range(1, 30):
if gcd(a, b) == 1:
assert mobius_one(a * b) == mobius_one(a) * mobius_one(b)
# জানা যোগফল: ∑_{d|n} μ(d) = [n == 1] (Mobius-এর সংজ্ঞাগত ধর্ম)
def divisors(n):
return [d for d in range(1, n + 1) if n % d == 0]
for n in range(1, 30):
s = sum(mobius_one(d) for d in divisors(n))
assert s == (1 if n == 1 else 0), f"∑μ(d) ভুল at {n}"
print(mobius_one(6)) # 1
print(mobius_one(30)) # -1
print(mobius_sieve(12)[1:]) # [1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def mobius_one(n):
if n == 1:
return 1
cnt = 0
p = 2
while p * p <= n:
if n % p == 0:
n //= p
cnt += 1
if n % p == 0:
return 0
```
trial division — p পেলে একবার ভাগ করে distinct prime গোনা (cnt) বাড়াই, তারপর সঙ্গে সঙ্গে দেখি p **আবার** ভাগ করে কি না; করলে p² আছে, সোজা return 0।
```
if n > 1:
cnt += 1
return -1 if cnt % 2 else 1
```
লুপ শেষে অবশিষ্ট n > 1 হলে সেটা একটা বড় prime — cnt বাড়াই। শেষে distinct prime সংখ্যা জোড় হলে +1, বিজোড় হলে −1।
```
def mobius_sieve(N):
mu = [1] * (N + 1)
...
for p in range(2, N + 1):
if not is_comp[p]:
for j in range(p, N + 1, p):
if j > p: is_comp[j] = True
mu[j] *= -1
for j in range(p*p, N + 1, p*p):
mu[j] = 0
```
প্রতিটা prime p-এর জন্য — তার সব গুণিতকের sign উল্টাই (একটা distinct prime যোগ হলো), আর গুণিতকদের composite হিসেবে mark করি। তারপর p²-এর সব গুণিতকের mu = 0 (square ভাগ করে)। এভাবে প্রতিটা সংখ্যা সঠিক ±1 বা 0 পায়।
বাকি test অংশে দুই version (one বনাম sieve) 1..500 মেলানো হয়, multiplicative property আর বিখ্যাত `∑_{d|n} μ(d) = [n=1]` ধর্মও যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
1
-1
[1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0]
সব test pass!
```
`mobius_one(6)` → 1 (2·3, দুই prime)। `mobius_one(30)` → −1 (2·3·5, তিন prime)। `mobius_sieve(12)[1:]` → পুরো μ(1..12) array, যা section 5-এর table-এর সাথে হুবহু। তার আগে দুই version-এর মিল, multiplicative, আর divisor-sum সব assert pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**mobius_one: O(√n)** এক সংখ্যার জন্য (trial division)। **mobius_sieve: O(N log log N)** পুরো 1..N-এর জন্য — Eratosthenes-এর মতোই, প্রতিটা prime তার গুণিতকদের একবার ছোঁয়। তাই বহুবার μ লাগলে sieve বানিয়ে নাও (একবার O(N log log N), তারপর প্রতিটা lookup O(1)); শুধু একটা μ চাইলে O(√n) যথেষ্ট।
### অতিরিক্ত জায়গা {#16-space-complexity}
**mobius_one: O(1)** — শুধু কয়েকটা variable। **mobius_sieve: O(N)** — mu array আর is_comp array, দুটোই N+1 আকারের। CP-তে N যদি 10⁶-10⁷ হয়, এই array memory-তে রাখা যায়; তার বেশি হলে segmented বা per-query factorization ভাবতে হয়।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **square check ভুলে যাওয়া** — কোনো prime দুবার এলে μ = 0; এই চেক বাদ দিলে square-যুক্ত সংখ্যায় ভুল ±1। mobius_one-এ `n % p == 0` দ্বিতীয়বার, sieve-এ p²-লুপ — এটাই square ধরে।
2. **distinct prime নয়, মোট prime গোনা** — sign নির্ভর করে **distinct** prime সংখ্যার উপর (square-free হলে তো মোট = distinct, আর square থাকলে μ এমনিতেই 0)।
3. **μ(1) ভুল ধরা** — μ(1) = 1 (convention)। কোড আলাদা করে এটা handle না করলে ভুল হতে পারে।
4. **sieve-এ sign আর zero-এর order গুলিয়ে ফেলা** — আগে সব গুণিতকের sign উল্টাও, তারপর p²-গুণিতকদের 0; উল্টো করলে 0-গুলোও sign খেয়ে ফেলবে। (এখানে 0-লুপ পরে চলে, তাই নিরাপদ।)
5. **বহুবার per-query factorize করা** — অনেকবার μ লাগলে sieve বানাও; প্রতিবার O(√n) করা বড় N-এ ধীর।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Coprime Pairs** (