# Level 2 — Modular Arithmetic (ঘড়ির কাঁটার গণিত)

[ধারণা](concept-notes.md) · [চিত্র ও উদাহরণ](visualization-ideas.md) · [সমস্যার তালিকা](problems/README.md) · [মূল উৎস](source-map.md) · [পুরো শেখার মানচিত্র](../roadmap.md)

> Level 0-তে `%` ছিল last digit বের করার কাঁচি, Level 1-এ divisibility-র পরীক্ষক। এই level-এ দেখব `%` আসলে একটা আস্ত **গণিতের জগৎ** খুলে দেয় — যেখানে সংখ্যারা ঘড়ির কাঁটার মতো ঘোরে, আর বিশাল বিশাল হিসাব ছোট্ট পরিসরে নেমে আসে।

## এই level এ কী শিখবে?

"10⁹ + 7 দিয়ে mod করে উত্তর দাও" — CP আর interview-তে এই লাইনটা বারবার দেখবে। কেন এই অদ্ভুত দাবি, আর কীভাবে mod-এর জগতে যোগ-গুণ-power-এমনকি **ভাগ** করা যায় — এই level-এর বিষয় সেটাই।

মূল idea গুলো:

- **Clock model** — mod m মানে m-ঘরের ঘড়ি; সব সংখ্যা 0 থেকে m−1 এ ঘুরে ঘুরে আসে
- **Mod-এর নিয়ম** — `(a+b) % m` আর `(a*b) % m` প্রতি step-এ mod নিলেও উত্তর একই; কেন ও কখন
- **কেন mod লাগে** — C++/Java-তে overflow, Python-এ বিশাল সংখ্যার slow arithmetic
- **Fast power** — square-and-multiply দিয়ে aᵇ mod m, O(log b)-তে
- **Modular inverse** — mod-এর জগতে ভাগের বদলি; Fermat's little theorem: `a⁻¹ = a^(p−2) mod p`
- **nCr mod p pipeline** — factorial + inverse factorial precompute (Level 3-এর জন্য অস্ত্র)
- **Cyclicity** — last digit-এর চক্র (2, 4, 8, 6, ...), clock word problems
- **Hashing-এ mod** — string-এর fingerprint বানানো
- **Pitfalls** — negative mod, mod 1, non-prime mod-এ Fermat অচল

## কেন এই level দরকার?

**Competitive programming (CP) এ:** উত্তর বিশাল হলে problem setter বলে "print answer mod 10⁹+7" — তখন mod arithmetic না জানলে problem-ই attempt করা যায় না। CSES-এর Exponentiation, Binomial Coefficients ধাঁচের problem সরাসরি এখানকার জিনিস। String hashing, matrix exponentiation, combinatorial counting — সবার ভিত এই level।

**Interview এ:** Pow(x, n) একটা common interview pattern — O(n) থেকে O(log n)-এ নামানোর গল্পটা interviewer শুনতে চায়। Hash function design-এর আলোচনাতেও mod-এর বোঝাপড়া কাজে দেয়। আর "কেন 10⁹+7" প্রশ্নটার উত্তর জানা থাকলে গভীরতা দেখানো যায়।

**পরের level গুলোতে:** Level 3-এর nCr mod p এখানকার inverse ছাড়া অচল; পরে combinatorial DP-তে (path counting, ways counting) প্রতি step-এ mod নেওয়াটাই রুটিন হয়ে যাবে। Hashing পরে string algorithm-এ পুরো অধ্যায়।

## Prerequisites

- [Level 0](../00-absolute-basics/README.md) — `%`, `//`, digit extraction
- [Level 1](../01-divisibility-prime-gcd-lcm/README.md) — prime, coprime, GCD; বিশেষ করে "coprime মানে gcd=1" আর Extended GCD-র সাথে অন্তত মুখচেনা পরিচয়
- Python-এ function লেখা, recursion-এর basic ধারণা

## Learning goals (checklist)

এই level শেষে নিজেকে জিজ্ঞেস করো:

- [ ] mod m-এর clock ছবিটা আঁকতে পারি, আর "17 ≡ 5 (mod 12)" এর মানে বলতে পারি
- [ ] `(a + b) % m = ((a % m) + (b % m)) % m` — নিয়মটা জানি আর কেন দরকার বুঝি
- [ ] গুণের একই নিয়ম জানি, আর জানি **ভাগে এই নিয়ম সরাসরি চলে না**
- [ ] কেন প্রতি step-এ mod নিতে হয় — overflow (C++/Java) আর slowness (Python) দুই কারণই বলতে পারি
- [ ] Square-and-multiply দিয়ে `pow(a, b, m)` নিজে হাতে লিখতে পারি আর dry run করতে পারি
- [ ] Modular inverse কী, কখন exist করে (gcd(a, m) = 1), আর Fermat দিয়ে কীভাবে বের হয় — জানি
- [ ] nCr mod p-এর factorial + inverse factorial pipeline-টা ধাপে ধাপে বলতে পারি
- [ ] Last digit cyclicity দিয়ে 7^222-এর last digit মুখে মুখে বের করতে পারি
- [ ] Python-এ negative `%`-এর আচরণ জানি (সবসময় non-negative) আর C++-এর সাথে পার্থক্য জানি
- [ ] Polynomial hashing-এ mod কেন লাগে — fingerprint analogy-তে ব্যাখ্যা করতে পারি

## Problem list

মোট 13টা problem — 5টা Easy, 7টা Medium, 1টা Hard। Hard-টা (nCr mod p) এই level-এর শিখর — আগেরগুলো ঠিকঠাক করলে ওটা আপনিই দাঁড়িয়ে যাবে।

### Easy

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 026 | [Remainder Basics](problems/026-remainder-basics.md) | mod basics | Classic exercise |
| 027 | [Modular Addition](problems/027-modular-addition.md) | (a+b)%m | Classic exercise |
| 028 | [Modular Multiplication](problems/028-modular-multiplication.md) | (a*b)%m | Classic exercise |
| 036 | [Cyclic Remainder Pattern](problems/036-cyclic-remainder-pattern.md) | cycle in powers | Classic exercise |
| 037 | [Clock Arithmetic Problems](problems/037-clock-arithmetic.md) | clock model | Classic exercise |

### Medium

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 029 | [Modular Exponentiation](problems/029-modular-exponentiation.md) | square & multiply | CP-Algorithms — <https://cp-algorithms.com/algebra/binary-exp.html>, CSES Exponentiation — <https://cses.fi/problemset/task/1095> |
| 030 | [Fast Power](problems/030-fast-power.md) | binary exponentiation | LeetCode Pow(x, n) — <https://leetcode.com/problems/powx-n/> |
| 031 | [Large Number Mod](problems/031-large-number-mod.md) | digit-by-digit mod | Classic exercise |
| 032 | [Modular Inverse Basic](problems/032-modular-inverse-basic.md) | Fermat inverse | CP-Algorithms — <https://cp-algorithms.com/algebra/module-inverse.html> |
| 033 | [Fermat Little Theorem](problems/033-fermat-little-theorem.md) | a^(p-1) ≡ 1 | CP-Algorithms module-inverse page |
| 035 | [Modular Division](problems/035-modular-division.md) | multiply by inverse | Classic exercise |
| 038 | [Hashing with Mod](problems/038-hashing-with-mod.md) | polynomial hash | CP-Algorithms — <https://cp-algorithms.com/string/string-hashing.html> |

### Hard

| # | Problem | Pattern | Source |
| --- | --- | --- | --- |
| 034 | [nCr mod Prime](problems/034-ncr-mod-prime.md) | factorial + inverse | CP-Algorithms — <https://cp-algorithms.com/combinatorics/binomial-coefficients.html> |

পুরো tracker table (status সহ) আছে [problems/README.md](problems/README.md)-তে।

## Recommended order

1. **026 → 037** — mod-এর basics আর clock model; ঘড়ির ছবিটা আগে মাথায় বসাও
2. **027 → 028** — যোগ আর গুণের নিয়ম; "প্রতি step-এ mod" অভ্যাসটা এখানেই গড়ো
3. **031** — digit-by-digit mod; Level 0-এর digit loop + mod-এর নিয়ম একসাথে
4. **036** — power-এর cycle; cyclicity-র অনুভব
5. **029 → 030** — fast power; এই level-এর engine (030-এ negative exponent twist)
6. **033 → 032 → 035** — Fermat → inverse → division; "mod-জগতে ভাগ" এর পুরো গল্প
7. **034 (Hard)** — nCr mod p pipeline; সব আগের জিনিস একসাথে
8. **038** — hashing; mod-এর একটা বাস্তব application দিয়ে শেষ

## Common mistakes (সাধারণ ভুল)

1. **শেষে গিয়ে একবারে mod নেওয়া** — `(a * b * c) % m` Python-এ ঠিক উত্তর দেবে, কিন্তু মাঝের সংখ্যা বিশাল হয়ে slow; C++/Java হলে সরাসরি overflow-এ ভুল উত্তর। অভ্যাস করো: **প্রতিটা যোগ/গুণের পরেই `% m`।**
2. **ভাগেও mod-এর নিয়ম খাটানো** — `(a / b) % m ≠ ((a % m) / (b % m)) % m`। mod-জগতে ভাগ মানে inverse দিয়ে গুণ — shortcut নেই।
3. **Negative-এ mod** — `(a - b) % m` এ a−b negative হতে পারে। Python-এ `%` সবসময় non-negative দেয় (রক্ষা!), কিন্তু C++-এ negative আসে। ভাষা-নিরপেক্ষ safe রূপ: `((a - b) % m + m) % m` — এটা লিখে অভ্যাস করো।
4. **Non-prime mod-এ Fermat চালানো** — `a^(m-2)` শুধু m prime হলে inverse দেয়। m = 10 হলে Fermat অচল; gcd(a, m) = 1 হলে Extended GCD লাগবে, আর gcd ≠ 1 হলে inverse-ই নেই।
5. **`pow(a, b)` লিখে তারপর `% m`** — Python-এ `pow(a, b, m)` (তিন argument!) ব্যবহার করো; নাহলে আগে অতিকায় সংখ্যা বানিয়ে তারপর mod — অর্থহীন slow।
6. **mod 1 ভুলে যাওয়া** — যেকোনো সংখ্যা mod 1 = 0। `m = 1` edge case-এ fast power-এর উত্তর 0 হওয়া উচিত, 1 না।
7. **Cyclicity-তে exponent-এর mod ভুল জায়গায়** — 7^222-এর last digit বের করতে exponent-কে cycle length 4 দিয়ে mod করো (222 % 4 = 2), base-কে না। আর remainder 0 এলে cycle-এর **শেষ** ঘরটা পড়তে হয়, প্রথমটা না।
8. **Hash-এ ছোট/খারাপ mod বাছা** — mod ছোট হলে collision বেশি; চল হলো বড় prime (যেমন 10⁹+7) আর base এমন নেওয়া যা character-সংখ্যার চেয়ে বড়।

## পরের level এ যাওয়ার আগে checklist

- [ ] 13টা problem-এর অন্তত 11টা নিজে solve করেছি
- [ ] `pow(3, 13, 10)` হাতে square-and-multiply দিয়ে dry run করেছি (binary 1101 ধরে)
- [ ] "কেন 10⁹+7" — দুটো কারণ বলতে পারি (বড় prime → Fermat চলে; int range-এ গুণফল ধরে — C++ প্রসঙ্গ)
- [ ] inverse(3) mod 7 = 5 — Fermat দিয়ে নিজে বের করেছি আর `3 × 5 % 7 = 1` মিলিয়েছি
- [ ] `((a - b) % m + m) % m` — কেন এই রূপ, এক লাইনে বলতে পারি
- [ ] nCr mod p-এর pipeline-এর 3টা ধাপ (factorial precompute → inverse factorial → query O(1)) মুখস্থ না, বুঝে বলতে পারি

সব টিক দিতে পারলে — চলো [Level 3: Counting & Combinatorics](../03-counting-combinatorics/README.md)-এ, যেখানে এই nCr-ই গোনাগুনতির রাজা হয়ে ফিরবে।

## Source map

এই folder-এর প্রতিটা concept আর problem কোথা থেকে এসেছে, কোন link official, আর কোনটা original লেখা — সব হিসাব আছে [source-map.md](source-map.md)-তে।