Concept Notes — Modular Arithmetic¶
এই level-এর কেন্দ্রে একটাই ছবি: ঘড়ি। প্রতিটা section-এ সেই ঘড়িটা মনে মনে চালাও। আর আগের মতোই — প্রতিটা dry run খাতায় নিজে হাতে।
1. Mod মানে ঘড়ির কাঁটা¶
12-ঘণ্টার ঘড়িতে এখন 9টা বাজে; 5 ঘণ্টা পরে কয়টা? 9 + 5 = 14 — কিন্তু ঘড়ি বলে 2টা। কারণ কাঁটা 12 পেরোলেই আবার শুরু থেকে: 14 % 12 = 2।
এটাই modular arithmetic-এর পুরো দর্শন: mod m মানে m-ঘরের একটা ঘড়ি, যেখানে সব সংখ্যা 0 থেকে m−1 এর মধ্যে ঘুরে ঘুরে আসে।
mod 5 এর ঘড়ি: number line ভাঁজ করে ঘড়ি বানানো:
0
4 1 0 1 2 3 4 | 5 6 7 8 9 | 10 11 12 ...
3 2 0 1 2 3 4 | 0 1 2 3 4 | 0 1 2 ...
প্রতি 5 ঘরে আবার শুরু — 7 আর 12 আর 2, ঘড়ির চোখে একই জন
গণিতবিদরা লেখে 7 ≡ 2 (mod 5) — পড়ো "7 আর 2 congruent mod 5", মানে দুজনকে 5 দিয়ে ভাগ করলে remainder একই। Level 0-এর digital root মনে আছে? সেই 9-ঘরের বৃত্ত — ওটা আসলে mod 9-এর ঘড়িই ছিল!
Negative-এ সাবধান: Python-এ -3 % 5 = 2 (সবসময় non-negative — ঘড়িতে পেছনে 3 ঘর হাঁটলে 2-তে পৌঁছাও)। কিন্তু C++-এ -3 % 5 = -3! ভাষা-নিরপেক্ষ safe অভ্যাস: ((x % m) + m) % m।
2. Mod-এর নিয়ম — প্রতি step-এ mod নিলেও ক্ষতি নেই¶
জাদুর নিয়ম দুটো:
মানে: যোগ বা গুণের আগে সবাইকে ঘড়ির ঘরে নামিয়ে নিলেও শেষ উত্তর একই। Intuition: a = q₁m + r₁, b = q₂m + r₂ লিখলে a + b = (q₁+q₂)m + (r₁+r₂) — m-এর গুণিতক অংশ ঘড়িতে পুরো চক্কর, কাঁটার অবস্থান ঠিক করে শুধু r₁+r₂। গুণেও একই: a×b ভাঙলে শুধু r₁×r₂ ছাড়া বাকি সব term-এ m আছে।
a, b, m = 1234, 5678, 7
print((a + b) % m) # 3
print(((a % m) + (b % m)) % m) # 3 -> একই!
print((a * b) % m) # 5
print(((a % m) * (b % m)) % m) # 5 -> একই!
Mini dry run: 1234 % 7 = 2 (1234 = 7×176 + 2), 5678 % 7 = 1 (5678 = 7×811 + 1)। যোগ: (2+1) % 7 = 3 ✓। গুণ: (2×1) % 7 = 2... দাঁড়াও, উপরে তো 5! আবার হিসাব: 5678 = 7×811 + 1? 7×811 = 5677, হ্যাঁ remainder 1। 1234 % 7: 7×176 = 1232, remainder 2। 2×1 = 2 % 7 = 2। তাহলে (1234×5678) % 7-ও 2 হওয়ার কথা — নিজে Python-এ চালিয়ে মিলিয়ে নাও; mismatch পেলে হাতের হিসাবেই ভুল আছে ধরে নিয়ে আবার করো। এই "মিলিয়ে দেখা"-টাই mod শেখার আসল practice।
⚠️ ভাগে এই নিয়ম নেই: (10 / 2) % 4 = 1, কিন্তু ((10%4) / (2%4)) % 4 = (2/2) % 4 = 1... এখানে মিলল, কিন্তু (12 / 6) % 4 = 2 আর ((12%4) / (6%4)) = 0/2 = 0 — মিলল না! mod-জগতে ভাগ আলাদা গল্প (section 6)।
3. কেন আদৌ mod লাগে?¶
ধরো n! বের করতে বলেছে, n = 10⁵। উত্তরটা প্রায় 4,56,574 digit-এর সংখ্যা!
- C++/Java: 64-bit int-এ ধরে প্রায় 9.2×10¹⁸ — 21!-এই overflow, উত্তর garbage।
- Python: int unbounded, overflow নেই — কিন্তু লাখো digit-এর সংখ্যার প্রতিটা গুণ ক্রমশ ধীর; পুরো হিসাব কয়েক সেকেন্ড থেকে মিনিটে গড়ায়, time limit শেষ।
সমাধান: problem setter বলে দেয় "উত্তরটা mod 10⁹+7 করে দাও।" তখন প্রতি step-এ mod নিলে সংখ্যা কখনোই 10⁹+7 ছাড়ায় না — ছোট, দ্রুত, নিরাপদ।
MOD = 10**9 + 7
def factorial_mod(n):
result = 1
for i in range(2, n + 1):
result = result * i % MOD # প্রতি step-এ mod!
return result
Mini dry run (n = 5, MOD = 7 — ছোট করে দেখি): result: 1 → 1×2%7=2 → 2×3%7=6 → 6×4%7=3 → 3×5%7=1। তো 5! % 7 = 1। Check: 120 = 7×17 + 1 ✓।
কেন 10⁹+7? (1) এটা prime — তাই Fermat-এর inverse চলে (section 6); (2) দুটো mod-করা সংখ্যার গুণফল ~10¹⁸ < 64-bit সীমা — C++ ব্যবহারকারীদের জন্য নিরাপদ। চলতি আরেকটা পছন্দ 998244353 (এটাও prime)।
4. Fast power — square-and-multiply¶
3^13 % 7 বের করতে 13 বার গুণ? চলে। কিন্তু 3^(10^18) % m? এক এক করে গুণলে মহাবিশ্বের আয়ু শেষ। কৌশল: exponent-কে binary-তে ভাবো।
13 = 1101₂ = 8 + 4 + 1
3¹³ = 3⁸ × 3⁴ × 3¹
আর 3¹, 3², 3⁴, 3⁸ — প্রতিটা আগেরটার square!
3¹ = 3
3² = 3¹ × 3¹ = 9
3⁴ = 3² × 3² = 81
3⁸ = 3⁴ × 3⁴ = 6561
মানে: base-কে বারবার square করো, আর exponent-এর binary-তে যেখানে যেখানে 1, সেখানকার power-টা উত্তরে গুণে নাও। 10¹⁸-এর জন্যও মোটে ~60 ধাপ — O(log b)।
def fast_pow(a, b, m):
result = 1
a %= m
while b > 0:
if b & 1: # exponent-এর last bit 1?
result = result * a % m
a = a * a % m # square
b >>= 1 # পরের bit-এ যাও
return result
Mini dry run (3^13 % 7):
| step | b (binary) | last bit | result | a (square হয়ে) |
|---|---|---|---|---|
| শুরু | 1101 | — | 1 | 3 |
| 1 | 1101 | 1 | 1×3 % 7 = 3 | 3×3 % 7 = 2 |
| 2 | 110 | 0 | 3 | 2×2 % 7 = 4 |
| 3 | 11 | 1 | 3×4 % 7 = 5 | 4×4 % 7 = 2 |
| 4 | 1 | 1 | 5×2 % 7 = 3 | 2×2 % 7 = 4 |
b শূন্য, উত্তর 3। Check: 3¹³ = 1594323 = 7×227760 + 3 ✓। Python-এ built-in আছে: pow(3, 13, 7) — তিন-argument pow, contest-এ এটাই লেখো; কিন্তু ভেতরের খেলাটা জানা থাকা চাই, interview-তে হাতে লিখতে বলবে।
5. Cyclicity — power-এর remainder ঘুরে ঘুরে আসে¶
2-এর power-গুলোর last digit দেখো:
2¹ 2² 2³ 2⁴ 2⁵ 2⁶ 2⁷ 2⁸ ...
2 4 8 16 32 64 128 256
last digit: 2, 4, 8, 6, 2, 4, 8, 6, ... -> 4 ঘর পরপর একই চক্র!
কেন? Last digit মানে mod 10 — আর mod 10-এর ঘড়িতে ঘর মোটে 10টা; power-এর ধারা একসময় আগের কোনো ঘরে ফিরবেই, আর ফিরলেই চক্র। তাই 2^222-এর last digit: cycle length 4, 222 % 4 = 2 → চক্রের 2 নম্বর ঘর → 4। (সাবধান: remainder 0 হলে চক্রের শেষ ঘর — যেমন 2^8 → 8%4=0 → ঘর 4 → digit 6।)
def last_digit_of_power(base, exp):
cycle = []
d = base % 10
while d not in cycle:
cycle.append(d)
d = d * base % 10
r = exp % len(cycle)
return cycle[r - 1] # r=0 হলে cycle[-1] — শেষ ঘর, ঠিকই কাজ করে
Mini dry run (7^222): 7-এর last digit cycle: 7, 9, 3, 1 (length 4)। 222 % 4 = 2 → ঘর 2 → 9। এই cyclicity-ই Fermat's theorem-এর হাতে-কলমে রূপ — পরের section-এ পুরো সূত্র।
6. Modular inverse — mod-জগতে ভাগের বদলি¶
mod-এর জগতে ভাগ নেই। কিন্তু সাধারণ গণিতেও "5 দিয়ে ভাগ" মানে আসলে "1/5 দিয়ে গুণ" — মানে এমন সংখ্যা দিয়ে গুণ, যাকে 5 দিয়ে গুণ করলে 1 হয়। mod-জগতে একই দাবি: a-এর inverse মানে এমন x, যাতে a·x ≡ 1 (mod m)।
যেমন mod 7-এ 3-এর inverse 5, কারণ 3 × 5 = 15 ≡ 1 (mod 7)। তাহলে "mod 7-এ 6-কে 3 দিয়ে ভাগ" = 6 × 5 % 7 = 30 % 7 = 2 — আর সত্যিই 2 × 3 = 6 ✓।
Inverse কখন আছে? শুধু যখন gcd(a, m) = 1 (Level 1-এর coprime!)। mod 6-এ 2-এর inverse নেই — 2-এর গুণের সারি 2,4,0,2,4,0,... কখনো 1 ছোঁয় না।
Fermat's little theorem: p prime আর a, p-এর multiple না হলে —
হাতে দেখো (p = 5): 2⁴ = 16 ≡ 1, 3⁴ = 81 ≡ 1, 4⁴ = 256 ≡ 1 — প্রত্যেকে p−1 ধাপে ঘুরে 1-এ ফেরে (section 5-এর cycle-এরই theorem-রূপ)। এখন দুই পাশ থেকে এক a খুলে নাও:
def mod_inverse(a, p): # p অবশ্যই prime, আর p % a != 0... না —
return pow(a, p - 2, p) # শর্ত: a % p != 0
Mini dry run (inverse of 3 mod 7): 3⁵ % 7 — fast power-এ: 3²=2, 3⁴=4, 3⁵=3⁴×3=4×3=12%7=5। Check: 3×5 = 15 % 7 = 1 ✓।
⚠️ m prime না হলে Fermat অচল — তখন Level 1-এর Extended GCD দিয়ে inverse বের করতে হয় (gcd(a,m)=1 হলে)। দেখলে তো — 019 problem-টা কেন intro করিয়েছিলাম!
7. nCr mod p — factorial pipeline (Level 3-এর অস্ত্র)¶
Level 3-এ শিখবে nCr = n! / (r! × (n−r)!)। কিন্তু mod-জগতে ভাগ নেই — inverse দিয়ে গুণ:
অনেক query থাকলে pipeline-টা এই 3 ধাপে:
MOD = 10**9 + 7
N = 10**6
# ধাপ 1: factorial precompute — O(N)
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
# ধাপ 2: inverse factorial — শেষেরটা Fermat-এ, বাকি পেছন থেকে
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % MOD # 1/(i-1)! = (1/i!) × i
# ধাপ 3: প্রতিটা query O(1)
def nCr(n, r):
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
Mini dry run (5C2 mod 7): fact: 1,1,2,6,24%7=3,120%7=1 → fact[5]=1। inv_fact[2] = inverse(2) = 2⁵%7 = 4 (check: 2×4=8≡1 ✓)। inv_fact[3] = inverse(6) = 6⁵%7 = 6 (check: 6×6=36≡1 ✓)। nCr = 1 × 4 × 6 % 7 = 24 % 7 = 3। আর সত্যি 5C2 = 10, 10 % 7 = 3 ✓।
ধাপ 2-এর পেছন-থেকে-হাঁটা কৌশলটা লক্ষ করো — N টা আলাদা Fermat call (প্রতিটা O(log p)) এর বদলে একটা Fermat + N টা গুণ। ছোট জিনিস, কিন্তু contest-এ এটাই TLE আর AC-র তফাত।
8. Large number mod আর hashing — mod-এর দুই বাস্তব রূপ¶
Large number mod: সংখ্যাটা যদি file-এ 10⁵ digit-এর string হয়ে আসে? পুরোটা int বানিয়ে mod — Python-এ চলে কিন্তু ধীর। চালাক উপায়: Level 0-এর "number building" (rev*10 + d) প্রতি ধাপে mod সহ —
Mini dry run ("1234" mod 7): r: 0 → (0×10+1)%7=1 → (1×10+2)%7=12%7=5 → (5×10+3)%7=53%7=4 → (4×10+4)%7=44%7=2। Check: 1234 = 7×176 + 2 ✓। দেখো — সংখ্যা কখনো 7×10+9 = 79 ছাড়ালই না!
Hashing: একটা string-কে একটা সংখ্যায় (fingerprint-এ) নামানো, যাতে দুটো string সমান কি না O(1)-এ আঁচ করা যায়। ধারণা: string-টাকে base-B সংখ্যা ভাবো —
লক্ষ করো — এটা হুবহু big_mod-এর কাঠামো, শুধু base 10-এর জায়গায় 31! mod না নিলে hash অসীম বড় হতো; mod নেওয়ায় ছোট থাকে, কিন্তু দাম দিতে হয়: ভিন্ন string-এর hash কালেভদ্রে মিলে যেতে পারে (collision) — যেমন আঙুলের ছাপও খুব ক্বচিৎ মিলে যায়। বড় prime mod নিলে সে সম্ভাবনা নগণ্য। পুরো hashing-এর গল্প পরে string algorithm-এ।
এক নজরে (cheat sheet)¶
a ≡ b (mod m) -> a আর b ঘড়ির একই ঘরে
(a+b) % m, (a*b) % m -> প্রতি step-এ mod নিরাপদ; ভাগে না!
((x % m) + m) % m -> negative-safe mod
pow(a, b, m) -> Python-এর fast power; নিজেরটা: square-and-multiply
a⁻¹ = a^(p−2) mod p -> Fermat inverse (p prime, a % p ≠ 0)
ভাগ mod p -> inverse দিয়ে গুণ
nCr mod p -> fact[] + inv_fact[] precompute, query O(1)
last digit cycle -> exponent % cycle_length; 0 হলে শেষ ঘর
big string mod -> r = (r*10 + digit) % m
hash -> r = (r*B + char) % M — একই কাঠামো!
পরের ধাপ: problems/-এর 13টা problem। তারপর Level 3 — যেখানে গুনব "কত উপায়ে" — আর বড় উত্তরগুলো সামলাতে আজকের nCr mod p pipeline-টাই হবে প্রধান হাতিয়ার।