Problem link ও উৎস
- **Original source:** CP-Algorithms — Euler's Totient Function
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 10: Advanced Number Theory
- **Difficulty:** Medium
- **Pattern:** multiplicative phi
- **Basic idea inherited from:** 023 (Basic Euler Totient)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বের করতে হবে **φ(n)** (Euler's totient) — মানে `1` থেকে `n`-এর মধ্যে কতগুলো সংখ্যা n-এর সাথে **coprime** (gcd = 1)।
উদাহরণ: φ(9) = 6, কারণ 1, 2, 4, 5, 7, 8 — এই 6টা সংখ্যা 9-এর সাথে coprime (3, 6, 9 নয়, কারণ ওদের সাথে 9-এর সাধারণ গুণনীয়ক 3)।
Level 2-এ আমরা প্রতিটা সংখ্যার gcd চেক করে গুনেছিলাম (O(n))। এবার লক্ষ্য — **prime factorization থেকে এক সূত্রে** φ(n), অনেক দ্রুত। মনে রেখো — এই level CP-leaning, interview-optional; কিন্তু φ-এর সূত্রটা modular গণিতের (Euler's theorem) মূল চাবিগুলোর একটা।
### Input ও output {#6-example-input-and-output}
```text
input n -> φ(n) কেন
----------------------------------------------------------------
1 -> 1 (1 নিজে coprime ধরা হয়; convention)
9 -> 6 1,2,4,5,7,8
36 -> 12 36·(1/2)·(2/3)
10 -> 4 1,3,7,9
7 -> 6 prime p -> φ(p) = p − 1
12 -> 4 1,5,7,11
100 -> 40 100·(1/2)·(4/5)
1 -> 1 edge case
```
খেয়াল করো: **prime p হলে φ(p) = p − 1** (1 থেকে p−1 সবাই coprime)। আর **prime power p^e হলে φ(p^e) = p^e − p^(e−1)** (যেমন φ(9) = 9 − 3 = 6)। edge case φ(1) = 1 (convention — 1 নিজের সাথে coprime ধরা হয়)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ক্লাসে n জন ছাত্র, সবাইকে 1 থেকে n নম্বর দেওয়া। তুমি এমন ছাত্রদের গুনতে চাও যাদের নম্বর n-এর সাথে coprime — যেন তারা "n-এর কোনো গুণনীয়ক-দলের সদস্য নয়"।
ধরো n = 12 = 2² · 3। দুটো "নিষিদ্ধ দল":
- **2-এর গুণিতকরা** (2, 4, 6, 8, 10, 12) — অর্ধেক ছাত্র বাদ → বাকি `12·(1 − 1/2) = 6`
- বাকিদের থেকে আবার **3-এর গুণিতকরা** বাদ → আরও এক-তৃতীয়াংশ যায় → `6·(1 − 1/3) = 4`
প্রতিটা prime একটা করে "ছাঁকনি" — 2 অর্ধেক ছাঁকে, 3 এক-তৃতীয়াংশ ছাঁকে, আর তারা **স্বাধীনভাবে** কাজ করে (coprime বলে ওভারল্যাপ হিসাব মিলে যায়)। শেষে যারা টিকে থাকে, তারাই φ(n) = 4 জন (1, 5, 7, 11)।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **023 (Basic Euler Totient)**-এর উপর। 023-তে আমরা φ(n)-এর সংজ্ঞা শিখেছিলাম আর gcd চেক করে গুনেছিলাম — O(n) পদ্ধতি। 128 সেই সংজ্ঞাকে রেখে গোনার বদলে **prime factorization-এর সূত্র** ব্যবহার করে, যা অনেক দ্রুত (O(√n))।
পেছনে আরও দাঁড়িয়ে আছে Level 1-এর prime factorization (trial division)। আর এর উপরে দাঁড়াবে **129 (Mobius)** — μ-ও একটা multiplicative function, তাই 128-এর "multiplicative" চিন্তাটা 129-এর ভিত্তি। README-র recommended order-এ তাই 128 → 129 পরপর।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **φ একটা multiplicative function**, আর তাই prime factorization থেকে এক সূত্রে বের হয়। n-এর factorization যদি হয় `p1^e1 · p2^e2 · ... · pk^ek`, তবে:
```
φ(n) = n · (1 − 1/p1) · (1 − 1/p2) · ... · (1 − 1/pk)
```
মানে n দিয়ে শুরু করে প্রতিটা **distinct prime** p-এর জন্য `(1 − 1/p)` দিয়ে গুণ — exponent কত তাতে কিছু আসে যায় না, শুধু কোন কোন prime আছে সেটাই গুরুত্বপূর্ণ। আর "multiplicative" মানে: `gcd(a, b) = 1` হলে `φ(a·b) = φ(a)·φ(b)`। এই level CP-leaning হলেও সূত্রটা চমৎকার সরল — প্রতিটা prime স্বাধীনভাবে নিজের ভাগ কাটে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
023-এর সরল পদ্ধতি — **1 থেকে n-এর প্রতিটা সংখ্যার সাথে n-এর gcd চেক করা**, gcd 1 হলে গুনে নাও:
```python
from math import gcd
def phi_brute(n):
count = 0
for i in range(1, n + 1):
if gcd(i, n) == 1:
count += 1
return count
```
ছোট n-এ (যেমন 36) এটা নিখুঁত — সরাসরি সংজ্ঞা থেকে গুনছে। আমাদের সূত্রের উত্তর এই brute force-এর সাথে মিলিয়ে যাচাই করব। শুরুর জন্য একদম পরিষ্কার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
loop ঘোরে ঠিক `n` বার, আর প্রতিবার একটা gcd (নিজেই O(log n))। তাই মোট O(n log n)-এর কাছাকাছি।
```text
n ছোট (36): 36 বার gcd — তাৎক্ষণিক
n = 10⁶: 10⁶ বার gcd — সেকেন্ড খানেক
n = 10¹²: 10¹² বার — অসম্ভব!
সূত্র (factorization): O(√n) — n = 10¹²-এও মাত্র ~10⁶ ধাপ
```
বড় n-এ brute force অচল। অথচ prime factorization trial division-এ O(√n)-এ হয়ে যায় (√(10¹²) = 10⁶), আর তার পর শুধু কয়েকটা গুণ — তাই সূত্র বিশাল দ্রুত।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **φ(n) গুনতে হয় না, prime factorization থেকে হিসাব করা যায়।** ধাপ:
```text
1. result = n দিয়ে শুরু
2. p = 2 থেকে √n পর্যন্ত প্রতিটা সম্ভাব্য prime p-এর জন্য:
যদি p | n:
n থেকে p-এর সব ভাগ সরিয়ে দাও (while n % p == 0: n //= p)
result -= result // p (অর্থাৎ result *= (1 − 1/p))
3. লুপ শেষে যদি n > 1 থাকে, সেটা একটা বড় prime factor — তার জন্যও:
result -= result // n
4. result-ই φ(মূল n)
```
কেন `result -= result // p` কাজ করে: এটা ঠিক `result · (1 − 1/p)`-এর integer রূপ, আর যেহেতু এই বিন্দুতে result সবসময় p-এর গুণিতক (n-এর factor বলে), ভাগটা নিঃশেষ হয়। প্রতিটা distinct prime একবারই এই কাটা প্রয়োগ করে — তাই exponent গুরুত্বহীন।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **φ multiplicative — তাই প্রতিটা prime নিজের ভাগটা স্বাধীনভাবে কাটে, exponent কত তাতে কিছুই যায় আসে না।**
brute force প্রতিটা সংখ্যা আলাদা যাচাই করছিল; tweak হলো — গোটা সংখ্যাকে prime-এ ভেঙে প্রতিটা distinct prime-এর জন্য মাত্র একবার `(1 − 1/p)` গুণ করো। O(n) গোনা থেকে O(√n) factorization-এ নেমে এল। আর multiplicative হওয়াতেই এই ভাঙা-জোড়া বৈধ — `φ(p^e) = p^e − p^(e−1)`, আর coprime অংশগুলো গুণ হয়।
### ছবিতে বোঝা {#5-visual-explanation}
φ(36)-এর সূত্র, ধাপে ধাপে — 36 = 2² · 3²:
```text
n = 36, factorization: 2² · 3²
distinct prime: শুধু 2 আর 3 (exponent গুরুত্বহীন)
result = 36
2 পেলাম: result = 36 − 36/2 = 36·(1/2) = 18 [2-এর গুণিতক ছাঁকা]
3 পেলাম: result = 18 − 18/3 = 18·(2/3) = 12 [3-এর গুণিতক ছাঁকা]
φ(36) = 12 ✓
multiplicative দিয়ে cross-check:
36 = 4 × 9, gcd(4, 9) = 1
φ(4) = 2 (1, 3 coprime), φ(9) = 6 (1,2,4,5,7,8)
φ(36) = φ(4)·φ(9) = 2·6 = 12 ✓ — দুই পথ একই উত্তর
```
লক্ষ করো — সূত্রে `result − result/p` লেখা হলো `result·(1 − 1/p)`-এরই integer রূপ (ভাঙা ভগ্নাংশ এড়াতে)। আর multiplicative property দিয়ে আলাদা করেও মিলিয়ে দেখা গেল।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`phi(36)` — সূত্র দিয়ে:
| step | p | n (অবশিষ্ট) | p | n? | result (শুরুতে 36) |
| --- | --- | --- | --- | --- |
| শুরু | — | 36 | — | result = 36 |
| 1 | 2 | 36 | হ্যাঁ (36%2=0) | n থেকে 2 সরাও: 36→18→9; result = 36 − 36//2 = 18 |
| 2 | 3 | 9 | হ্যাঁ (9%3=0) | n থেকে 3 সরাও: 9→3→1; result = 18 − 18//3 = 12 |
| শেষ | — | 1 | n = 1, তাই n > 1 শর্ত মিথ্যা | result = 12 |
φ(36) = **12** ✓। লক্ষ করো — 2 আর 3 প্রতিটা একবারই কাটল (exponent 2 হলেও), আর n অবশিষ্ট হিসেবে 1-এ নেমে গেল বলে শেষ `n > 1` ধাপ লাগল না।
আরেকটা: `phi(10)` — 10 = 2 · 5:
| step | p | n অবশিষ্ট | result |
| --- | --- | --- | --- |
| শুরু | — | 10 | 10 |
| 1 | 2 | 10 → 5 | 10 − 10//2 = 5 |
| লুপ শেষ | — | 5 | 5 > 1, তাই result = 5 − 5//5 = 4 |
φ(10) = **4** ✓ (এখানে 5 বড় prime হিসেবে শেষ ধাপে কাটল)।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def phi(n):
"""Euler's totient φ(n) — prime factorization-এর সূত্রে, O(√n)।"""
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0: # p-এর সব ভাগ সরাও
n //= p
result -= result // p # result *= (1 − 1/p)
p += 1
if n > 1: # অবশিষ্ট বড় prime factor
result -= result // n
return result
def phi_multiplicative(a, b):
"""coprime a, b হলে φ(a·b) = φ(a)·φ(b) — property যাচাইয়ের জন্য।"""
from math import gcd
assert gcd(a, b) == 1
return phi(a) * phi(b)
# --- ছোট test গুলো (সব pass করা উচিত) ---
from math import gcd
def phi_brute(n):
return sum(1 for i in range(1, n + 1) if gcd(i, n) == 1)
# সূত্র vs brute force — 1..300 সব মেলাও
for n in range(1, 301):
assert phi(n) == phi_brute(n), f"φ({n}) ভুল: {phi(n)} != {phi_brute(n)}"
# কিছু known মান
assert phi(1) == 1
assert phi(9) == 6
assert phi(36) == 12
assert phi(10) == 4
assert phi(7) == 6 # prime -> p − 1
assert phi(100) == 40
# prime power: φ(p^e) = p^e − p^(e−1)
assert phi(8) == 8 - 4 # 2³
assert phi(27) == 27 - 9 # 3³
# multiplicative property: gcd=1 হলে φ(ab) = φ(a)φ(b)
assert phi(36) == phi_multiplicative(4, 9)
assert phi(100) == phi_multiplicative(4, 25)
assert phi(35) == phi(5) * phi(7)
# বড় সংখ্যা — দ্রুত
assert phi(1000000) == 400000
print(phi(36)) # 12
print(phi(100)) # 40
print(phi(1000000)) # 400000
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```
def phi(n):
result = n
p = 2
while p * p <= n:
```
result-কে n দিয়ে শুরু করছি (তারপর প্রতিটা prime-এর জন্য কমাব)। p 2 থেকে √n পর্যন্ত ঘোরাই — √n-এর বড় কোনো prime factor বড়জোর একটাই থাকতে পারে, সেটা পরে আলাদা সামলাব।
```
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
```
p যদি n-এর গুণনীয়ক হয় — প্রথমে n থেকে p-এর সব ঘাত সরিয়ে দিই (যাতে p আর বিবেচিত না হয়), তারপর result থেকে `result // p` বিয়োগ। এটাই `result · (1 − 1/p)`-এর integer রূপ।
```
if n > 1:
result -= result // n
```
লুপ শেষে n যদি 1-এর বড় থাকে, সেটা একটা বড় prime factor (√(মূল n)-এর চেয়ে বড়) — তার জন্যও একবার `(1 − 1/n)` কাটা প্রয়োগ। যেমন φ(10)-তে 5।
```
def phi_multiplicative(a, b):
assert gcd(a, b) == 1
return phi(a) * phi(b)
```
multiplicative property সরাসরি — coprime হলে `φ(a·b) = φ(a)·φ(b)`। assert নিশ্চিত করে আমরা সত্যিই coprime জোড়া দিচ্ছি।
বাকি test অংশে 1 থেকে 300 পর্যন্ত সূত্র আর brute force মিলিয়ে দেখা হয়, prime/prime-power/multiplicative সব ক্ষেত্রে যাচাই হয়। সব ঠিক থাকলে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```
12
40
400000
সব test pass!
```
`phi(36)` → 12 (36·½·⅔), `phi(100)` → 40 (100·½·⅘), `phi(1000000)` → 400000 (10⁶ = 2⁶·5⁶, তাই 10⁶·½·⅘ = 400000) — আর এই বড় সংখ্যাটাও তাৎক্ষণিক, কারণ trial division O(√n)। তার আগে 1..300-এর সব মান brute force-এর সাথে মিলেছে, সব assert pass — তাই `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — trial division-এ p 2 থেকে √n পর্যন্ত ঘোরে। প্রতিটা division/বিয়োগ O(1) (Python-এর বড় সংখ্যায় সামান্য বেশি, কিন্তু সাধারণ মাপে O(1) ধরি)। তাই n = 10¹²-এও মাত্র ~10⁶ ধাপ — brute force-এর O(n log n)-এর তুলনায় বিশাল লাফ। (একাধিক n-এর φ একসাথে চাইলে sieve-ভিত্তিক O(n log log n) আরও ভালো, যা 137-এ আসবে।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো array লাগছে না, শুধু গুটিকয় variable (result, p, n)। একটামাত্র সংখ্যার φ বের করতে এটাই যথেষ্ট। (একসাথে অনেক সংখ্যার φ চাইলে sieve-এ O(n) array লাগবে — আলাদা বিষয়।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **প্রতিটা distinct prime-এর বদলে প্রতিটা ঘাতে কাটা** — `(1 − 1/p)` প্রতিটা distinct prime-এর জন্য মাত্র **একবার**; exponent যত-ই হোক। তাই p পেলে আগে তার সব ঘাত n থেকে সরিয়ে দাও।
2. **অবশিষ্ট বড় prime ভুলে যাওয়া** — লুপ √n পর্যন্ত; n যদি শেষে 1-এর বড় থাকে, সেটা বড় prime, তার `result -= result // n` লাগবেই (যেমন φ(10)-এর 5)।
3. **float দিয়ে `result * (1 − 1/p)`** — ভগ্নাংশে round-off ভুল। সবসময় integer-এ `result -= result // p` করো।
4. **φ(1) ভুল ধরা** — convention অনুযায়ী φ(1) = 1; সূত্র এমনিতেই এটা দেয় (লুপ চলে না, n = 1), তাই আলাদা করে কিছু না করলেও ঠিক।
5. **n modify করার পর মূল n দরকার হলে গুলিয়ে ফেলা** — এখানে result আগে n দিয়ে set করা হয়েছে; তারপর n ভাঙা হচ্ছে — order ঠিক রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CSES — Counting Coprime Pairs / Common Divisors** (