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

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 — %, //, digit extraction
Level 1 — 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	mod basics	Classic exercise
027	Modular Addition	(a+b)%m	Classic exercise
028	Modular Multiplication	(a*b)%m	Classic exercise
036	Cyclic Remainder Pattern	cycle in powers	Classic exercise
037	Clock Arithmetic Problems	clock model	Classic exercise

Medium¶

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

Hard¶

#	Problem	Pattern	Source
034	nCr mod Prime	factorial + inverse	CP-Algorithms — https://cp-algorithms.com/combinatorics/binomial-coefficients.html

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

Recommended order¶

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

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

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

Source map¶

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