Problem link ও উৎস
- **Original source:** CP-Algorithms — Euler's totient function
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Medium
- **Pattern:** totient formula — φ(n) = n · ∏(1 − 1/p)
- **Basic idea inherited from:** 016 — Prime Factorization; 021 — Coprime Check
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা ধনাত্মক integer `n` দেওয়া আছে। বের করতে হবে **φ(n)** (Euler's phi, বা totient) — মানে 1 থেকে n পর্যন্ত কয়টা সংখ্যা n-এর সাথে coprime (gcd 1)।
উদাহরণ: φ(12) বের করতে 1..12-এর মধ্যে দেখি কারা 12-এর সাথে coprime — শুধু **1, 5, 7, 11** (বাকিরা 2 বা 3 share করে)। তাই φ(12) = 4।
কয়েকটা চেনা মান: φ(1) = 1 (শুধু 1 নিজে), আর p prime হলে φ(p) = p − 1 (1 থেকে p−1 সবাই p-র সাথে coprime, কারণ p-র একমাত্র factor সে নিজে)।
### Input ও output {#6-example-input-and-output}
```text
n -> φ(n) কেন
-----------------------------------
1 -> 1 শুধু 1 নিজে
2 -> 1 শুধু 1 (prime, p−1 = 1)
9 -> 6 1,2,4,5,7,8 (3 আর 6 বাদ)
10 -> 4 1,3,7,9
12 -> 4 1,5,7,11
13 -> 12 prime -> p−1 = 12
36 -> 12 36 = 2^2·3^2 -> 36·1/2·2/3 = 12
100 -> 40 100 = 2^2·5^2 -> 100·1/2·4/5 = 40
```
দুটো জিনিস খেয়াল করো: **p prime হলে φ(p) = p − 1** (13 → 12)। আর একই distinct prime থাকলে power যত-ই হোক formula-তে prime একবারই বসে — 12 (2²·3) আর 36 (2²·3²) দুটোরই distinct prime {2,3}, কিন্তু φ আলাদা কারণ সামনে n আলাদা (12 vs 36)।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো 12 জনের একটা দল, আর তুমি জোড়ায় নাচ আয়োজন করবে — কিন্তু শর্ত: একজন partner-এর সাথে নাচতে গেলে তাদের "ছন্দ" মিলতে হবে, মানে তারা coprime হতে হবে। তুমি গুনতে চাও — 12 নম্বরের সাথে কতজন (1..12) ছন্দ মেলায়।
হাতে গুনতে গেলে সবাইকে একে একে যাচাই করতে হয় (1 মেলে, 2 মেলে না কারণ দুজনেই 2-এর ঘরে, ...)। কিন্তু একটা শর্টকাট আছে: 12-এর "বাধা" শুধু তার prime উপাদান 2 আর 3। প্রথমে 2-এর ঘরের অর্ধেককে বাদ দাও, তারপর বাকিদের থেকে 3-এর ঘরেরদের বাদ দাও — যা টিকে থাকে, তারাই ছন্দ মেলায়। সেই "ভাগে ভাগে বাদ দেওয়া"-ই phi-র formula।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দুটো আগের idea-র উপর দাঁড়িয়ে:
- **016 (Prime Factorization)** — φ-র formula চালাতে আগে n-এর distinct prime গুলো জানা চাই। আমরা ছোট prime দিয়ে n-কে "খোসা ছাড়িয়ে" সেই prime গুলো বের করি (016-এর কৌশল), শুধু এবার power গোনার বদলে প্রতিটা distinct prime একবার ব্যবহার করি।
- **021 (Coprime Check)** — φ-র সংজ্ঞাটাই "coprime কয়টা"; gcd == 1-এর ধারণা না থাকলে φ-ই মানে রাখে না। (Brute force version-এ আমরা সরাসরি 021-এর coprime check প্রতিটা সংখ্যায় চালাব।)
তাই আটকালে: formula-তে আটকালে 016-এ ফিরে factorization ঝালাও; "coprime মানে কী"-তে আটকালে 021।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো factorization থেকে আসা একটা **product formula**। n-এর distinct prime গুলো p₁, p₂, ... হলে:
```text
φ(n) = n · (1 − 1/p₁) · (1 − 1/p₂) · ...
```
মানে n নাও, তারপর প্রতিটা distinct prime p-র জন্য `(1 − 1/p)` দিয়ে গুণ করো।
কেন? 1..n-এর মধ্যে অর্ধেক সংখ্যা 2-এর গুণিতক — তারা 2 share করে, তাই বাদ; টিকে থাকে `× (1 − 1/2)` ভাগ। সেই টিকে থাকাদের এক-তৃতীয়াংশ 3-এর গুণিতক — বাদ, টিকে `× (1 − 1/3)`। প্রতিটা prime ক্রমে "কিছু অংশ কেটে দেয়" — sieve-এর crossing-out-এরই ভগ্নাংশ-রূপ। শুধু **distinct** prime লাগে (একই prime-এর power বারবার নয়)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
φ-র সংজ্ঞা সরাসরি ধরে — 1 থেকে n পর্যন্ত প্রতিটা সংখ্যা ঘুরে দেখি কে n-এর সাথে coprime, গুনি:
```python
def phi_brute(n):
from math import gcd
count = 0
for k in range(1, n + 1):
if gcd(k, n) == 1: # 021-এর coprime check
count += 1
return count
```
এটা একদম সংজ্ঞা: 1..n-এর প্রতিটা k-র জন্য gcd(k, n) == 1 হলে count বাড়াই। 021-এর coprime check-ই এখানে n বার চালানো হচ্ছে। সরল, ঠিক উত্তর, আর formula-র উত্তর verify করার জন্য চমৎকার।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
এই loop ঠিক `n` বার ঘোরে, প্রতিবার একটা gcd (O(log n))। তাই খরচ O(n log n)।
```text
n = 1,000 -> ~1,000 gcd (চোখের নিমেষে)
n = 1,000,000 -> ~10^6 gcd (ঠিক আছে, সেকেন্ড খানেক)
n = 10^12 -> ~10^12 gcd (অসম্ভব — TLE)
```
মূল সমস্যা: n বিশাল হলে 1..n ঘোরা অসম্ভব। অথচ formula-তে আমরা শুধু n-এর prime factor গুলো খুঁজি (O(√n) সময়), তারপর গুটিকয় গুণ — n যত বড়ই হোক, কাজ √n-এই সীমাবদ্ধ। সেটাই দ্রুত পথ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — **φ গুনতে 1..n ঘোরার দরকার নেই; n-এর distinct prime জানলে formula-তেই উত্তর।**
`φ(n) = n · ∏(1 − 1/p)`। বাস্তবে float এড়াতে আমরা ভগ্নাংশ ব্যবহার না করে integer-এ লিখি: প্রতিটা distinct prime p পেলে `result` থেকে `result // p` বিয়োগ করি — কারণ `result × (1 − 1/p) = result − result/p`:
```python
def phi(n):
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0: # এই prime-কে নিঃশেষে ছাড়াই
n //= p
result -= result // p # result × (1 − 1/p), integer-এ
p += 1
if n > 1: # বাকি যা, সে নিজেই বড় prime
result -= result // n
return result
```
মূল চালাকি দুটো: (1) প্রতিটা distinct prime একবারই `result` কমায় (ভেতরের while দিয়ে power সব ছেঁটে ফেলি); (2) শেষের `if n > 1` — n-এর সবচেয়ে বড় prime factor (যদি সে √n-এর চেয়ে বড় হয়) ধরার জন্য।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **`result × (1 − 1/p)` মানে আসলে `result − result/p` — তাই float ছাড়াই, শুধু integer বিয়োগ দিয়ে phi হিসাব হয়।**
আর দ্বিতীয় মোচড়: formula-তে **distinct** prime লাগে, power নয়। তাই 8 = 2³ হলেও φ-তে 2 একবারই বসে — `φ(8) = 8 × (1 − 1/2) = 4`, তিনবার নয়। এই "power উপেক্ষা করো, distinct prime নাও" আর "ভগ্নাংশকে বিয়োগে বদলাও" — এই দুই tweak মাথায় গেঁথে নাও।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে হাতে-গোনা — 1..12-এর মধ্যে কারা 12-এর সাথে coprime:
```text
n = 12, distinct prime: 2, 3
1 2 3 4 5 6 7 8 9 10 11 12
✓ ✗ ✗ ✗ ✓ ✗ ✓ ✗ ✗ ✗ ✓ ✗
| | | |
coprime: 1 5 7 11 -> φ(12) = 4
(✗ = 2 বা 3 share করে)
```
এবার formula কীভাবে একই 4 দেয়:
```text
12 = 2^2 · 3^1 -> distinct prime { 2, 3 }
φ(12) = 12 · (1 − 1/2) · (1 − 1/3)
= 12 · 1/2 · 2/3
= 12 · (1/3)
= 4 ✓ (হাতে-গোনার সাথে মিলল)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো phi(12) ধীরে চালাই। শুরুতে `result = 12`, `n = 12`:
| p | n % p == 0? | ভেতরের while: n হয় | result বদল | result |
| --- | --- | --- | --- | --- |
| 2 | হ্যাঁ | 12→6→3 | 12 − 12//2 = 12 − 6 | 6 |
| 3 | 3·3 > 3, loop শেষ | — | — | 6 |
Loop-এর পরে `n = 3 > 1`, তাই শেষ ধাপ: `result -= result // n` → `6 − 6//3 = 6 − 2 = 4`।
φ(12) = **4** — section 5-এর হাতে-গোনা 1,5,7,11-এর সাথে হুবহু মিলল। লক্ষ করো 2-এর power (2²) থাকলেও `result` একবারই কমেছে, কারণ ভেতরের while সব 2 নিঃশেষ করেছে আগেই।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def phi(n):
"""1..n-এর মধ্যে কয়টা সংখ্যা n-এর সাথে coprime — Euler totient।"""
if n <= 0:
return 0
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0: # distinct prime: power সব ছাঁটো
n //= p
result -= result // p # result × (1 − 1/p)
p += 1
if n > 1: # বাকি n নিজেই একটা বড় prime
result -= result // n
return result
def phi_brute(n):
"""সংজ্ঞা ধরে: 1..n-এ coprime গোনা — formula verify করতে।"""
from math import gcd
return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert phi(1) == 1
assert phi(2) == 1
assert phi(9) == 6
assert phi(10) == 4
assert phi(12) == 4
assert phi(13) == 12 # prime -> p−1
assert phi(36) == 12
assert phi(100) == 40
assert phi(7919) == 7918 # বড় prime -> p−1
# formula আর brute force ছোট range-এ মিলছে কি না
for m in range(1, 50):
assert phi(m) == phi_brute(m)
print(phi(12)) # 4
print(phi(13)) # 12
print(phi(100)) # 40
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
result = n
p = 2
while p * p <= n:
```
`result` শুরুতে n (formula-র সামনের n)। তারপর √n পর্যন্ত প্রতিটা সম্ভাব্য prime p দেখি — কারণ n-এর কোনো prime factor √n-এর এপারে অবশ্যই থাকে (বড়জোর একটা ছাড়া)।
```text
if n % p == 0:
while n % p == 0:
n //= p
```
p যদি n-কে ভাগ করে, সে একটা prime factor। ভেতরের while দিয়ে p-কে নিঃশেষে ছাড়াই (n থেকে সব p সরিয়ে দিই) — যাতে প্রতিটা distinct prime একবারই গোনা হয়।
```text
result -= result // p
```
এটাই formula-র হৃদয়: `result × (1 − 1/p)`-কে integer-এ লেখা। float এড়িয়ে শুধু বিয়োগ।
```text
if n > 1:
result -= result // n
```
Loop শেষে n যদি এখনো 1-এর বেশি হয়, সেটা n-এর সবচেয়ে বড় prime factor (√n-এর চেয়ে বড়, তাই loop ধরেনি)। তাকেও একবার গুণে নিই। (যেমন n = 14 = 2×7: loop-এ 2 ধরা পড়ে, n হয়ে যায় 7, তারপর 7 এই লাইনে।)
`phi_brute` সংজ্ঞা ধরে গোনে; নিচের `for m in range(1, 50)` loop দুই version মিলিয়ে formula-র correctness যাচাই করে। সব ঠিক থাকলে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
4
12
40
সব test pass!
```
প্রথম লাইন: φ(12) = 4 (section 11-এর dry run)। দ্বিতীয়: φ(13) = 12 (prime, তাই p−1)। তৃতীয়: φ(100) = 40 (100 = 2²·5² → 100·1/2·4/5 = 40)। তার আগে সব `assert`, এমনকি 1..49 জুড়ে formula-vs-brute মিল — সব চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(√n)** — মূল loop p চলে 2 থেকে √n পর্যন্ত (এটাই factorization-এর খরচ)। ভেতরের while-গুলো মিলিয়েও মোট কাজ O(√n)-এই থাকে (n বারবার ভাগ হয়ে দ্রুত ছোট হয়)। তাই n = 10¹² হলেও √n = 10⁶ — এক লহমায় শেষ। brute force-এর O(n log n)-এর তুলনায় বিশাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `result`, `p`, আর পরিবর্তিত `n` — গুটিকয় variable। কোনো list, array বা sieve বানাচ্ছি না (এটা single-n basic version)। (অনেকগুলো n একসাথে লাগলে sieve দিয়ে O(n) জায়গায় সব φ precompute করা যায় — Level 2-র গল্প।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **distinct prime-এর বদলে power গোনা** — 8 = 2³-এ 2 একবারই formula-তে বসে; ভেতরের while দিয়ে power ছেঁটে না ফেললে `result` বারবার কমে ভুল হবে।
2. **শেষের `if n > 1` ভুলে যাওয়া** — n-এর বড় prime factor (যেমন 14-এর 7, বা 7919) এই লাইন ছাড়া ধরা পড়ে না, φ ভুল আসে।
3. **float ব্যবহার করা** — `result * (1 - 1/p)` সরাসরি float-এ করলে rounding ভুল; integer বিয়োগ `result -= result // p` নিরাপদ।
4. **n ≤ 0 বা n = 1 ভুলে যাওয়া** — φ(1) = 1 (loop চলে না, result থাকে 1 — ঠিক); n ≤ 0 আমরা 0 ধরি।
5. **prime-এর জন্য φ(p) = p ভাবা** — সঠিক হলো p − 1 (p নিজে p-র সাথে coprime নয়)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Euler's totient function** (