Problem link ও উৎস
- **Original source:** CP-Algorithms (inclusion-exclusion)
- **Platform:** CP-Algorithms —
- **Topic:** Math-based programming fundamentals → Level 3: Counting & Combinatorics
- **Difficulty:** Medium
- **Pattern:** overcount correction (inclusion-exclusion)
- **Basic idea inherited from:** 041 — Combination Basic (set-গোনা আর overcount শোধরানোর ভাবনা)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কয়েকটা দল (set) আছে। জানতে চাই **অন্তত একটা দলে** কতগুলো জিনিস আছে — মানে দলগুলোর **union**-এর আকার।
ভুল উত্তর: সব দলের আকার যোগ করা। কারণ যেসব জিনিস **একাধিক দলে** আছে, তারা বারবার গোনা হয়ে যায়।
সবচেয়ে সহজ রূপ (দুই দল): `|A ∪ B|` বের করা — A বা B (বা দুটোতেই) আছে এমন জিনিস কয়টা।
ক্লাসিক CP রূপ: 1 থেকে N-এ কয়টা সংখ্যা `a` **বা** `b` দিয়ে ভাগ যায়?
### Input ও output {#6-example-input-and-output}
```text
দুই দল union:
|A|=25, |B|=18, |A∩B|=10 -> 33
1..N-এ a বা b দিয়ে ভাগ যায় (count_divisible):
N=100, a=2, b=3 -> 67 (50 + 33 − 16)
N=100, a=2, b=5 -> 60 (50 + 20 − 10)
N=15, a=3, b=5 -> 7 (5 + 3 − 1)
তিন দল union:
|A|=|B|=|C|=10, সব জোড়া=3, মাঝ=1 -> 10·3 − 3·3 + 1 = 22
```
Edge case: দুই দলে কোনো overlap না থাকলে (`|A∩B| = 0`) union = `|A| + |B|` — বিয়োগ কিছু নেই। আর সব দল এক হলে union = একটা দলের আকার।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তোমার ক্লাসে দুটো ক্লাব — cricket আর football। শিক্ষক জানতে চান **অন্তত একটা** ক্লাবে কতজন আছে।
cricket-এ 25, football-এ 18। সরাসরি যোগ করলে 43। কিন্তু যারা **দুটো ক্লাবেই** নাম লিখিয়েছে (ধরো 10 জন), তাদের তো একবার cricket-এ, একবার football-এ — **দুবার** গুনে ফেললে!
তাই সেই 10 জনকে একবার বিয়োগ করো: `25 + 18 − 10 = 33`। এই "দুই জায়গায় থাকা মানুষকে একবার বাদ" — এটাই inclusion-exclusion-এর হৃদয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা **041 (Combination Basic)**-এর চিন্তা-ধারার আত্মীয়: সেখানে nCr-এ একই দল r! বার গোনা হয়েছিল, তাই **r! দিয়ে ভাগ করে overcount শোধরেছিলাম।** এখানেও মূল সুর সেই — গোনার সময় কিছু জিনিস বেশিবার গোনা পড়ে, সেটা **যোগ-বিয়োগ করে** শোধরানো।
পার্থক্য: 041-এ একই গুণিতকে overcount (তাই ভাগ), এখানে overlapping set-এ overcount (তাই বিয়োগ-যোগ)। আর কোন intersection কতবার গোনা হলো সেটা বুঝতে combination-এর `C(set, j)` চিন্তাও লুকিয়ে আছে — তাই 041 ভিত্তি।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **যা বেশিবার গুনলে, সেটা বিয়োগ করে শোধরাও।**
দুই দলে:
```text
|A ∪ B| = |A| + |B| − |A ∩ B|
```
`|A| + |B|`-এ দুই দলেই থাকা জিনিসগুলো (intersection) দুবার গোনা হয়, তাই একবার বিয়োগ।
তিন দলে ঢেউটা আরেক ধাপ গড়ায়:
```text
|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
```
**নিয়ম (মন্ত্র):** বিজোড় সংখ্যক দলের intersection **যোগ**, জোড় সংখ্যকের **বিয়োগ** — পালা করে।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরাসরি — **সব জিনিস একে একে দেখে set-এ ফেলে গোনা।** যেমন 1..N-এ a বা b দিয়ে ভাগ যায় কয়টা:
```python
def count_divisible_brute(N, a, b):
count = 0
for x in range(1, N + 1):
if x % a == 0 or x % b == 0:
count += 1
return count
```
প্রতিটা সংখ্যা ঘুরে দেখি ভাগ যায় কিনা — একদম ঠিক উত্তর, আর formula verify করার নিখুঁত উপায়। সাধারণ union-এর জন্য Python-এর `set` দিয়ে union করেও সরাসরি গোনা যায়।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো এই loop **N বার** চলে। N ছোট হলে ঠিক আছে, কিন্তু:
```text
N = 10^9, a = 2, b = 3 হলে:
brute force: 100 কোটি বার loop -> Time Limit Exceeded
inclusion-exclusion: N//2 + N//3 − N//6 -> মাত্র 3 টা ভাগ, O(1)!
```
বড় range-এ একে একে গোনা অসম্ভব ধীর, অথচ formula এক নিমেষে উত্তর দেয়। আর set দিয়ে union করলে memory-ও O(N) — বিশাল N-এ অচল।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: একে একে না গুনে **প্রতিটা set কত বড় সেটা সরাসরি হিসাব করো, তারপর overlap বিয়োগ করো।**
1..N-এ a-এর গুণিতক ঠিক `N // a` টা — গোনা লাগে না! তাই:
```python
def count_divisible(N, a, b):
from math import gcd
lcm = a * b // gcd(a, b) # a আর b দুটোতেই ভাগ = lcm-এর গুণিতক
return N // a + N // b - N // lcm
```
`N // lcm` কেন? "a **এবং** b দুটোতেই ভাগ যায়" মানে lcm(a, b)-এর গুণিতক (Level 1-এর gcd/lcm এখানে ফিরল!)। তিন বা বেশি set-এ একই নিয়ম bitmask দিয়ে সাধারণ করা যায় (section 12)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা" মুহূর্ত: **আগে সব যোগ করে নাও যেন overlap নেই — তারপর যতবার বেশি গুনলে, ততবার বিয়োগ-যোগ করে শোধরাও।**
একটা জিনিস যদি ঠিক j টা set-এ থাকে, naive যোগে সে j বার গোনা হয়; inclusion-exclusion-এর পালা-নাচ (যোগ − জোড়া + ত্রয়ী − ...) ঠিক এমনভাবে সাজানো যে শেষে সে **ঠিক একবার** গোনা হয়। এই "overcount-কে পালা করে শোধরাও" চিন্তাটাই অস্ত্র — আর "এবং" মানে intersection (সংখ্যায় lcm) — এই দুই গেঁথে নাও।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে দেখো Venn diagram-এ কেন বিয়োগ লাগে (cricket 25, football 18, দুটোই 10):
```text
cricket (25) football (18)
+-------------+---------+-------------+
| | | |
| 15 | 10 | 8 |
| (শুধু crick) | (দুটোই) | (শুধু foot) |
| | | |
+-------------+---------+-------------+
মাঝের 10 দুই বৃত্তেই -> |A|+|B|-এ দুবার গোনা
তাই একবার বিয়োগ: 25 + 18 − 10 = 33
আলাদা করে: 15 + 10 + 8 = 33 ✓
```
এবার দেখো তিন দলে কীভাবে যোগ-বিয়োগ পালা করে:
```text
|A∪B∪C| = +|A| +|B| +|C| (একক -> যোগ)
−|A∩B| −|B∩C| −|A∩C| (জোড়া -> বিয়োগ)
+|A∩B∩C| (তিন -> যোগ)
মাঝের (তিনটাতেই থাকা) জিনিস: যোগে 3 বার, জোড়ায় 3 বার বিয়োগ
-> এখন 0 বার! তাই শেষে একবার ফেরত যোগ
```
লক্ষ করো — প্রতিটা জিনিস ঠিক একবার গোনা হওয়ার জন্যই এই পালা-নাচ।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
চলো `N = 100, a = 2, b = 3` চালাই:
| ধাপ | হিসাব | মান |
| --- | --- | --- |
| 2-এর গুণিতক | 100 // 2 | 50 |
| 3-এর গুণিতক | 100 // 3 | 33 |
| lcm(2,3) = 6 | — | 6 |
| 6-এর গুণিতক (দুটোই) | 100 // 6 | 16 |
| union | 50 + 33 − 16 | **67** |
মানে 1..100-এ 67টা সংখ্যা 2 বা 3 দিয়ে ভাগ যায়।
হাতে যাচাই (ছোট, N=15, a=3, b=5): 3-এর গুণিতক {3,6,9,12,15} = 5টা, 5-এর {5,10,15} = 3টা, 15-এর {15} = 1টা → 5+3−1 = 7। তালিকা: {3,5,6,9,10,12,15} — ঠিক 7টা ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
from math import gcd
def union_two(a_size, b_size, inter_size):
"""|A ∪ B| = |A| + |B| − |A ∩ B|।"""
return a_size + b_size - inter_size
def count_divisible(N, a, b):
"""1..N-এ a বা b দিয়ে ভাগ যায় এমন সংখ্যা কয়টা।"""
lcm = a * b // gcd(a, b)
return N // a + N // b - N // lcm
def count_divisible_any(N, divisors):
"""1..N-এ divisors-এর যেকোনোটি দিয়ে ভাগ যায় কয়টা (general inclusion-exclusion)।
প্রতিটা অ-খালি উপসেট ঘুরি: বিজোড় সংখ্যক হলে যোগ, জোড় হলে বিয়োগ;
সেই উপসেটের সব divisor-এর lcm-এর গুণিতক = N // lcm।
"""
from math import lcm as _lcm
m = len(divisors)
total = 0
for mask in range(1, 1 << m): # 1 থেকে 2^m − 1
cur_lcm = 1
bits = 0
for i in range(m):
if mask & (1 << i):
cur_lcm = _lcm(cur_lcm, divisors[i])
bits += 1
cnt = N // cur_lcm
if bits % 2 == 1: # বিজোড় -> যোগ
total += cnt
else: # জোড় -> বিয়োগ
total -= cnt
return total
# --- brute force verifier ---
def count_divisible_brute(N, divisors):
count = 0
for x in range(1, N + 1):
if any(x % d == 0 for d in divisors):
count += 1
return count
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert union_two(25, 18, 10) == 33
assert union_two(10, 5, 0) == 15 # overlap নেই
assert count_divisible(100, 2, 3) == 67
assert count_divisible(100, 2, 5) == 60
assert count_divisible(15, 3, 5) == 7
# দুই-divisor formula == general == brute (ছোট range জুড়ে)
for N in range(0, 60):
for a in range(2, 7):
for b in range(2, 7):
f = count_divisible(N, a, b)
g = count_divisible_any(N, [a, b])
br = count_divisible_brute(N, [a, b])
assert f == g == br
# তিন-divisor general == brute
for N in range(0, 40):
assert count_divisible_any(N, [2, 3, 5]) == count_divisible_brute(N, [2, 3, 5])
print(union_two(25, 18, 10)) # 33
print(count_divisible(100, 2, 3)) # 67
print(count_divisible_any(100, [2, 3, 5])) # 74
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
def union_two(a_size, b_size, inter_size):
return a_size + b_size - inter_size
```
দুই দলের মূল formula — যোগ করে, দুবার গোনা intersection একবার বিয়োগ।
```text
def count_divisible(N, a, b):
lcm = a * b // gcd(a, b)
return N // a + N // b - N // lcm
```
1..N-এ a-এর গুণিতক `N//a`, b-এর `N//b`, "দুটোই" মানে lcm(a,b)-এর গুণিতক `N//lcm` — সেটাই বিয়োগ।
```text
for mask in range(1, 1 << m):
... cur_lcm = lcm(...) ...
if bits % 2 == 1: total += cnt
else: total -= cnt
```
general version — প্রতিটা অ-খালি উপসেট (bitmask) ঘুরি, সেই divisor-গুলোর lcm-এর গুণিতক গুনি; উপসেটে দল-সংখ্যা বিজোড় হলে যোগ, জোড় হলে বিয়োগ — এটাই পালা-নাচ।
বাকি `assert` লাইনগুলো formula, general আর brute force — তিন পথ মিলিয়ে যাচাই করছে। সব মিললে শেষে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
33
67
74
সব test pass!
```
প্রথম: `union_two(25,18,10)` = 33। দ্বিতীয়: `count_divisible(100,2,3)` = 67। তৃতীয়: 1..100-এ 2/3/5 দিয়ে ভাগ যায় = 74 (`50+33+20 − 16−10−6 + 1`)। আগের সব `assert` (formula বনাম general বনাম brute) চুপচাপ pass করেছে। শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
দুই/তিন নির্দিষ্ট set-এর formula **O(1)** (গুটিকয় ভাগ)। general version-এ m টা set হলে `2^m` টা উপসেট × প্রতিটায় O(m) lcm = **O(2ᵐ · m)** — m ছোট (যেমন ≤ 20) থাকলে দ্রুত। brute force-এর O(N)-এর তুলনায় বিশাল N-এ আকাশ-পাতাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু গুটিকয় variable (mask, lcm, total); কোনো বড় set বা list রাখা হয় না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **Intersection বিয়োগ ভুলে যাওয়া** — `|A|+|B|` লিখে থেমে যাওয়া; **− |A∩B|**-ই পদ্ধতির প্রাণ।
2. **তিন set-এ মাঝেরটা ফেরত যোগ না করা** — তিন-intersection শেষে **+** দিয়ে ফিরবে, নাহলে সে 0 বার গোনা থাকবে।
3. **"এবং" মানে lcm না বোঝা** — "a আর b দুটোতেই ভাগ" = lcm(a,b)-এর গুণিতক, `a×b`-এর নয় (যদি a,b coprime না হয়)।
4. **খালি উপসেট গোনা** — general-এ mask 0 (কোনো set না) বাদ দিতে হবে; তাই `range(1, ...)`।
5. **যোগ/বিয়োগ চিহ্ন উল্টানো** — বিজোড় দল = যোগ, জোড় দল = বিয়োগ; এক ধাপ ভুল হলেই উত্তর নষ্ট।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **CP-Algorithms — Inclusion-Exclusion** (