Problem link ও উৎস
- **Original source:** Classic exercise
- **Platform:** Classic exercise / — (judge-free)
- **Topic:** Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
- **Difficulty:** Medium
- **Pattern:** gcd over all pairs (i < j)
- **Basic idea inherited from:** 021 — Coprime Check
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
ধনাত্মক integer-এর একটা list দেওয়া আছে। বের করতে হবে — এর মধ্যে কতগুলো **জোড়া** (pair) পরস্পর coprime, মানে যাদের gcd ঠিক 1।
জোড়া বলতে আমরা বুঝি দুটো **আলাদা position**-এর সংখ্যা, আর `(i, j)` ও `(j, i)` একই জোড়া — তাই একবারই গুনব। সাজানোর ক্রম গুরুত্বপূর্ণ নয়।
উদাহরণ: list = [2, 3, 4] হলে সম্ভাব্য জোড়া তিনটে — (2,3), (2,4), (3,4)। এদের মধ্যে (2,3) coprime, (3,4) coprime, কিন্তু (2,4) coprime নয় (gcd 2)। তাই উত্তর **2**।
### Input ও output {#6-example-input-and-output}
```text
list -> coprime pairs
---------------------------------------
[2, 3, 4] -> 2 (2,3) আর (3,4)
[1, 2, 3, 4] -> 5 1 সবার সাথে coprime: (1,2)(1,3)(1,4) + (2,3)(3,4)
[6, 10, 15] -> 0 তিনজনেরই কোনো-না-কোনো common factor
[5, 7, 11] -> 3 তিনটেই prime -> সব জোড়া coprime
[4] -> 0 একটামাত্র উপাদান, কোনো জোড়া নেই
[] -> 0 খালি list
[2, 2, 3] -> 2 (2,3) দুবার (দুটো 2-ই 3-এর সাথে); (2,2) নয়
```
দুটো জিনিস খেয়াল করো: **1 সব কিছুর সাথে coprime**, তাই list-এ 1 থাকলে সে প্রতিটা জোড়ায় coprime যোগ করে। আর [6,10,15] মজার — কোনো একটা সংখ্যা সবার সাথে common factor share করে না, কিন্তু *প্রতিটা জোড়ায়* কোনো-না-কোনো common factor আছে (6&10→2, 6&15→3, 10&15→5), তাই উত্তর 0।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ঘরে কয়েকজন মানুষ আছে, আর তুমি জানতে চাও — কতগুলো জোড়া পরস্পর **handshake** করতে পারে। প্রত্যেকে প্রত্যেকের সাথে একবারই হাত মেলায়, আর "ক হাত মেলাল খ-র সাথে" আর "খ হাত মেলাল ক-র সাথে" — একই handshake, দুবার গোনা যাবে না।
আমাদের problem-এ সেই handshake-টা শর্তসাপেক্ষ: দুজন তখনই "মেলে" যখন তারা coprime (gcd 1)। তাই আমরা প্রতিটা সম্ভাব্য জোড়া একবার করে দেখি, আর শুধু coprime জোড়াগুলো গুনি। `i < j` শর্তটাই নিশ্চিত করে কোনো handshake দুবার গোনা হচ্ছে না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **021 (Coprime Check)**-এর উপর দাঁড়িয়ে। 021-এ আমরা *একটা* জোড়া coprime কি না বলতাম; এখানে সেই check-টাই *সব* জোড়ায় চালাই আর গুনি।
মূল নতুন জিনিস coprime-এ নয় — সেটা 021 থেকে ready। নতুন জিনিস হলো **"সব জোড়া কীভাবে ঠিক একবার করে দেখব"** — সেই `i < j` কৌশল। তাই coprime অংশে আটকালে 021-এ ফিরে যাও; pair গোনায় আটকালে নিচের visualization দেখো।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea দুটো জিনিসের সংমিশ্রণ:
- **coprime check** = `gcd(a, b) == 1` (021 থেকে)।
- **সব জোড়া দেখা** = list-এর প্রতিটা দুই-উপাদানের সমাবেশ (combination) একবার করে দেখা, মানে `i < j` ধরে দুটো nested loop।
মোট জোড়ার সংখ্যা `n` উপাদানের জন্য `n × (n−1) / 2` (এটাই "n থেকে 2 বাছার" সংখ্যা — Level 3-এর combination-এর আগাম দর্শন)। প্রতিটা জোড়ায় gcd চালিয়ে 1 হলে count বাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — প্রতিটা সম্ভাব্য জোড়া ঘুরে gcd দেখি, 1 হলে গুনি। দুটো nested loop, বাইরেরটা `i`, ভেতরেরটা `j = i+1` থেকে (যাতে i < j):
```python
def count_coprime_pairs_brute(arr):
from math import gcd
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n):
if gcd(arr[i], arr[j]) == 1:
count += 1
return count
```
বাইরের loop প্রতিটা উপাদান ধরে, ভেতরের loop তার পরের সব উপাদানের সাথে জোড়া বানায় — তাই প্রতিটা জোড়া ঠিক একবার। gcd 1 হলে count বাড়ে। সরল, ঠিক উত্তর দেয়, আর এই level-এ এটাই গ্রহণযোগ্য সমাধান।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
জোড়ার সংখ্যা `n × (n−1) / 2` — মানে প্রায় **O(n²)** জোড়া, আর প্রতিটায় একটা gcd (O(log max))। তাই মোট খরচ O(n² · log max)।
```text
n = 100 -> ~4,950 জোড়া (চোখের নিমেষে)
n = 1,000 -> ~499,500 জোড়া (এখনো ঠিক আছে)
n = 100,000 -> ~5×10^9 জোড়া (অনেক ধীর — TLE)
```
ছোট-মাঝারি n-এ এই O(n²) ঠিক আছে (তাই Difficulty Medium, basic version)। কিন্তু n বিশাল হলে এটা ধীর — তখন Euler phi / Möbius-ভিত্তিক চালাকি লাগে (Level 2+)। এখন আমরা সচেতনভাবে সরল O(n²)-ই রাখছি, কারণ এটা বুঝতে সহজ আর correctness যাচাই করা যায়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
এই "basic" version-এর মূল লক্ষ্য দ্রুততা নয়, **সঠিকতা আর পরিষ্কার pair-গোনা**। তাই সবচেয়ে বড় insight এখানে algorithmic চমক নয়, বরং সতর্কতা:
- প্রতিটা জোড়া **ঠিক একবার** গোনো — `j` শুরু করো `i + 1` থেকে, `0` থেকে নয়। তাহলে (i, j) আর (j, i) দুবার গোনা হবে না, আর কোনো উপাদান নিজের সাথে (i == j) জোড়া বাঁধবে না।
- gcd-কে রি-ইনভেন্ট কোরো না — 018-এর Euclid বা Python-এর `math.gcd` ব্যবহার করো।
```python
def count_coprime_pairs(arr):
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n): # i < j: প্রতি জোড়া একবার
if gcd(arr[i], arr[j]) == 1:
count += 1
return count
```
(বড় n-এ চালাকি দরকার হলে: প্রতিটা সংখ্যার count রেখে Euler phi / inclusion-exclusion দিয়ে O(max·log) করা যায় — কিন্তু সেটা Level 2-র গল্প।)
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত এখানে efficiency-র চেয়ে correctness-এর: **জোড়া গোনার সময় ভেতরের loop সবসময় `i + 1` থেকে শুরু করো — এই একটা ছোট শর্তই দ্বিগুণ গোনা আর নিজে-জোড়া দুটো ভুল একসাথে আটকায়।**
মূল মোচড়টা মনে গাঁথো: `n` জিনিস থেকে 2টা বাছার সংখ্যা `n(n−1)/2`, আর সেটা পেতে nested loop-এ ভেতরেরটা বাইরেরটার পরে শুরু করতে হয়। এই "upper-triangle only" প্যাটার্ন pair-ভিত্তিক যেকোনো problem-এ ফিরবে (closest pair, pair sum, ইত্যাদি)।
### ছবিতে বোঝা {#5-visual-explanation}
list = [2, 3, 4]-এর সব জোড়া একটা ত্রিভুজাকার ছকে (শুধু i < j):
```text
j=0(2) j=1(3) j=2(4)
i=0(2) - (2,3) (2,4)
i=1(3) - - (3,4)
i=2(4) - - -
শুধু উপরের ত্রিভুজ (i < j) দেখি — নিচেরটা একই জোড়ার পুনরাবৃত্তি।
```
এবার প্রতিটা জোড়ায় gcd চালিয়ে সিদ্ধান্ত:
```text
(2,3): gcd 1 -> coprime ✓ count = 1
(2,4): gcd 2 -> না ✗ count = 1
(3,4): gcd 1 -> coprime ✓ count = 2
মোট coprime জোড়া = 2
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো arr = [2, 3, 4] ধীরে চালাই। count শুরুতে 0:
| i | j | arr[i] | arr[j] | gcd | coprime? | count |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 2 | 3 | 1 | হ্যাঁ | 1 |
| 0 | 2 | 2 | 4 | 2 | না | 1 |
| 1 | 2 | 3 | 4 | 1 | হ্যাঁ | 2 |
বাইরের loop i = 0,1 (i = 2-এ ভেতরের loop খালি, কারণ j শুরু 3 থেকে যা n-এর বাইরে)। তিনটে জোড়া ঠিক একবার দেখা হলো, দুটো coprime — শেষ **count = 2**। section 5-এর ছকের সাথে হুবহু মিলল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import gcd
def count_coprime_pairs(arr):
"""arr-এর মধ্যে কতগুলো জোড়া (i < j) coprime (gcd == 1) — গোনে।"""
n = len(arr)
count = 0
for i in range(n):
for j in range(i + 1, n): # i < j: প্রতি জোড়া ঠিক একবার
if gcd(arr[i], arr[j]) == 1:
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert count_coprime_pairs([2, 3, 4]) == 2 # (2,3),(3,4)
assert count_coprime_pairs([1, 2, 3, 4]) == 5 # 1 সবার সাথে + (2,3),(3,4)
assert count_coprime_pairs([6, 10, 15]) == 0 # প্রতি জোড়ায় common factor
assert count_coprime_pairs([5, 7, 11]) == 3 # তিনটেই prime
assert count_coprime_pairs([4]) == 0 # একটাই উপাদান
assert count_coprime_pairs([]) == 0 # খালি list
assert count_coprime_pairs([2, 2, 3]) == 2 # (2,3) দুবার, (2,2) নয়
assert count_coprime_pairs([8, 9, 25]) == 3 # 2^3, 3^2, 5^2 -> সব coprime
print(count_coprime_pairs([2, 3, 4])) # 2
print(count_coprime_pairs([1, 2, 3, 4])) # 5
print(count_coprime_pairs([6, 10, 15])) # 0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
from math import gcd
```
Python-এর built-in gcd — 018-এর Euclid এখানে আবার লিখে রি-ইনভেন্ট করার দরকার নেই, ready টুল ব্যবহার করি।
```text
n = len(arr)
count = 0
```
list-এর দৈর্ঘ্য রাখি, আর coprime জোড়ার গোনা 0 থেকে শুরু।
```text
for i in range(n):
for j in range(i + 1, n):
```
দুই nested loop — এটাই সব জোড়া ঘোরার অংশ। গুরুত্বপূর্ণ: `j` শুরু `i + 1` থেকে, যাতে (i, j) আর (j, i) দুবার না গোনা হয় আর i == j (নিজে-জোড়া) এড়ানো যায়।
```text
if gcd(arr[i], arr[j]) == 1:
count += 1
```
প্রতিটা জোড়ায় gcd দেখি; ঠিক 1 হলে coprime, তাই count বাড়াই। শেষে `return count`।
বাকি `assert` লাইনগুলো নিজেদের চেক করছে (খালি list, একক উপাদান, prime-only সহ নানা ক্ষেত্র); সব ঠিক থাকলে শেষে `সব test pass!` ছাপে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2
5
0
সব test pass!
```
প্রথম লাইন: [2,3,4] → 2 (section 11-এর dry run)। দ্বিতীয়: [1,2,3,4] → 5 — 1 প্রতিটা অন্যটার সাথে coprime (3টা জোড়া) + (2,3) + (3,4) = 5। তৃতীয়: [6,10,15] → 0, কারণ প্রতিটা জোড়ায় common factor। আগের সব `assert` চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n² · log max)** — জোড়ার সংখ্যা প্রায় n²/2 (nested loop), আর প্রতিটায় একটা gcd যার খরচ O(log max), যেখানে max হলো list-এর সবচেয়ে বড় সংখ্যা। ছোট-মাঝারি n-এ ঠিক আছে; বিশাল n-এ ধীর (তখন phi/Möbius লাগে)।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `count`, `i`, `j` — গুটিকয় variable। কোনো বাড়তি list বা array বানাচ্ছি না; input list-টাই শুধু পড়ছি।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **প্রতিটা জোড়া দুবার গোনা** — ভেতরের loop `0` থেকে শুরু করলে (i, j) আর (j, i) দুবার গোনা হবে, উত্তর দ্বিগুণ। সবসময় `j = i + 1` থেকে।
2. **উপাদানকে নিজের সাথে জোড়া বাঁধা** — `j` যদি `i` থেকে শুরু হয়, তাহলে (i, i) জোড়াও গোনা হবে; gcd(x, x) = x, ভুল ফল। `i + 1` এটা ঠেকায়।
3. **শেষে দুবার-গোনা ভেবে 2 দিয়ে ভাগ করা** — `i < j` ব্যবহার করলে আগে থেকেই একবার করে গোনা; আবার ভাগ করলে ভুল।
4. **মান বনাম position গুলিয়ে ফেলা** — [2, 2, 3]-এ দুটো 2 আলাদা position, তাই (2,3) দুবার গোনা ঠিক (উত্তর 2)। আমরা position-এর জোড়া গুনছি, distinct মানের নয়।
5. **খালি/একক list ভুলে যাওয়া** — n < 2 হলে কোনো জোড়াই নেই, উত্তর 0; loop এমনিতেই চলে না, তবু মাথায় রেখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Euler's totient function** (