Skip to content

Level 10 — Advanced Number Theory (সংখ্যাতত্ত্বের গভীরে)

⚠️ আগে পড়ো: এই level (আর level 11) big-tech interview-এর জন্য optional — interview-তে extended Euclid বা Miller-Rabin প্রায় আসে না। এগুলো competitive programming-এর জন্য deep material। তাই চাইলে এখন skip করে মূল DS topic গুলোতে (02-13) চলে যাও, সেগুলো শেষ করার পরেও এখানে ফিরে আসা যায় — কিছুই হারাবে না। আর CP-তে আগ্রহ থাকলে — স্বাগতম, এখানে সংখ্যার সবচেয়ে সুন্দর গল্পগুলো অপেক্ষা করছে।

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

Level 1-2-তে gcd, mod, prime-এর হাতেখড়ি হয়েছিল। এবার সেই hatiyar গুলোকে শান দেওয়ার পালা — শুধু "gcd কত" নয়, "gcd-টা কীভাবে বানানো হলো" (extended Euclid); শুধু "prime কি না" নয়, "10¹⁸ পর্যন্ত সংখ্যায় কয়েক microsecond-এ prime check" (Miller-Rabin)।

মূল idea গুলো:

  • Extended Euclid — ax + by = gcd(a, b)-এর x, y খুঁজে বের করা; Euclid-এর সিঁড়ি বেয়ে নিচে নেমে back-substitution-এ উপরে ওঠা
  • Linear Diophantine — ax + by = c solvable ⟺ gcd(a, b) | c; এক solution থেকে অসীম solution-এর পরিবার
  • CRT (Chinese Remainder Theorem) — দুটো আলাদা ঘড়ির reading মিলিয়ে আসল সময় বের করা; modulus merge
  • Totient advanced — φ multiplicative; prime factorization থেকে এক লাইনে φ(n)
  • Mobius function (μ) — inclusion-exclusion-কে একটা function-এ encode করা; "ঠিক gcd 1" ঘরানার গোনায় জাদু
  • Modular inverse (general) — prime modulus না হলেও ext-gcd দিয়ে inverse, যতক্ষণ gcd(a, m) = 1
  • Matrix exponentiation — recurrence-কে matrix-এ বদলে binary exponentiation; Fibonacci-র n-তম পদ O(log n)-এ
  • Fast doubling — Fibonacci-র জন্য matrix-এরও shortcut: F(2k)-এর সরাসরি formula
  • Miller-Rabin — probabilistic primality test; 64-bit-এর জন্য নির্দিষ্ট base-এ deterministic
  • Pollard rho — বড় সংখ্যার factorization; birthday paradox-এর উপর দাঁড়ানো cycle-খোঁজা
  • Sieve variants — smallest prime factor (SPF) sieve, linear sieve, আর segmented sieve — একই ছাঁকনির তিন রূপ

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

Competitive programming (CP) এ: Codeforces Div 2 D/E আর Div 1-এ number theory নিয়মিত মুখ। CRT, Mobius, matrix exponentiation — এগুলো ছাড়া অনেক problem-এর দরজাই খোলে না। আর CSES-এর Mathematics section পুরোটাই এই level-এর খেলার মাঠ।

Interview এ: সরাসরি খুব কম — তবে modular inverse আর fast exponentiation-এর চিন্তাভঙ্গি (divide and conquer on exponent) মাঝে মাঝে কাজে লাগে। আবারও মনে করিয়ে দিই: interview target হলে এই level পরে করলেও চলবে।

পরের level গুলোতে: Level 11-এর matrix power on graphs (147) সরাসরি 131-এর উপর দাঁড়ানো; আর Mobius-এর inclusion-exclusion চিন্তা 148-এ ফিরবে।

Prerequisites

  • Level 1-2 ভালোভাবে ঝালাই — বিশেষ করে:
  • gcd / Euclid (problem 018, 019) — extended Euclid এর সরাসরি extension
  • Modular arithmetic, Fermat inverse (problem 032), binary exponentiation (problem 029)
  • Basic totient (problem 023), sieve (problem 015), trial division primality (problem 013)
  • Level 3-এর inclusion-exclusion (problem 044) — Mobius বুঝতে লাগবে
  • Recursion-এ স্বচ্ছন্দ — extended Euclid আর fast doubling দুটোই recursive ভাবলে সহজ

Learning goals (checklist)

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

  • [ ] Extended Euclid-এ back-substitution-এর সিঁড়িটা একটা ছোট উদাহরণে (যেমন gcd(30, 18)) হাতে চালাতে পারি
  • [ ] ax + by = c কখন solvable — শর্তটা আর তার কারণ বলতে পারি
  • [ ] CRT-র "দুটো ঘড়ি মেলানো" গল্পটা একটা সংখ্যার উদাহরণে দেখাতে পারি
  • [ ] φ(n) prime factorization থেকে বের করার formula জানি, আর φ multiplicative মানে কী বুঝি
  • [ ] μ(n)-এর তিনটা মান (1, −1, 0) কখন হয় — মুখস্থ না, যুক্তিসহ জানি
  • [ ] Modular inverse-এর দুই পথ (Fermat আর ext-gcd) — কখন কোনটা লাগে জানি
  • [ ] Fibonacci-র matrix form [[1,1],[1,0]] কেন কাজ করে — এক ধাপ গুণ করে দেখাতে পারি
  • [ ] Miller-Rabin-এ "witness" মানে কী, আর কেন কয়েকটা নির্দিষ্ট base-এ 64-bit deterministic হয় — ধারণা আছে
  • [ ] SPF sieve দিয়ে O(log n)-এ factorization করতে পারি, আর segmented sieve কখন লাগে জানি

Problem list

মোট 14টা problem — 6টা Medium, 8টা Hard। (Easy নেই — এটা advanced level!)

Medium

# Problem Pattern Source
125 Extended Euclidean Algorithm back substitution CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html
126 Linear Diophantine Equation gcd divisibility CP-Algorithms — https://cp-algorithms.com/algebra/linear-diophantine-equation.html
128 Euler Totient Advanced multiplicative phi CP-Algorithms — https://cp-algorithms.com/algebra/phi-function.html
130 Modular Inverse Advanced ext-gcd inverse CP-Algorithms — https://cp-algorithms.com/algebra/module-inverse.html
134 Primality Test Advanced beyond trial division CP-Algorithms — https://cp-algorithms.com/algebra/primality_tests.html
137 Sieve Variants SPF / linear sieve CP-Algorithms — https://cp-algorithms.com/algebra/prime-sieve-linear.html

Hard

# Problem Pattern Source
127 Chinese Remainder Theorem Basic modulus merge CP-Algorithms — https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
129 Mobius Function Intro IE encoding Wikipedia — https://en.wikipedia.org/wiki/M%C3%B6bius_function
131 Matrix Exponentiation recurrence as matrix Classic CP technique (USACO Guide — https://usaco.guide/)
132 Fibonacci using Matrix Exponentiation matrix power CP-Algorithms Fibonacci — https://cp-algorithms.com/algebra/fibonacci-numbers.html
133 Fast Doubling Fibonacci F(2k) formulas CP-Algorithms Fibonacci page
135 Miller-Rabin Intro probabilistic test CP-Algorithms primality tests page
136 Pollard Rho Intro cycle factoring CP-Algorithms — https://cp-algorithms.com/algebra/factorization.html
138 Segmented Sieve windowed sieve CP-Algorithms sieve page — https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

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

  1. 125 → 126 → 130 — extended Euclid trilogy: আগে x, y বের করা শেখো, তারপর Diophantine, তারপর তা দিয়ে inverse
  2. 127 — CRT; 125-এর সরাসরি প্রয়োগ, তাই এর ঠিক পরে
  3. 128 → 129 — totient ঝালাই, তারপর Mobius; দুটোই multiplicative function-এর জগৎ
  4. 131 → 132 → 133 — matrix exponentiation trilogy: general কাঠামো → Fibonacci → fast doubling shortcut
  5. 134 → 135 → 136 — primality trilogy: trial division-এর সীমা → Miller-Rabin → Pollard rho
  6. 137 → 138 — sieve variants দিয়ে শেষ; এগুলো বাকি সবার toolbox

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

  1. Extended Euclid-এ x, y-এর update rule গুলিয়ে ফেলা — recursion থেকে ফেরার সময় x, y = y1, x1 − (a // b) * y1 — একটা ছোট উদাহরণে হাতে verify না করে কখনো use কোরো না।
  2. Diophantine-এ gcd | c check না করেই solution খোঁজা — solvability শর্তটাই প্রথম লাইন; না মিললে সোজা "no solution"।
  3. CRT-তে moduli coprime কি না না দেখা — basic CRT coprime moduli ধরে নেয়; coprime না হলে আলাদা merge-নিয়ম (general CRT) লাগে।
  4. Modular inverse-এ gcd(a, m) ≠ 1 ধরা না — inverse-এর অস্তিত্বই নেই তখন; Fermat শুধু prime m-এ চলে, ext-gcd চলে coprime হলেই।
  5. Matrix exponentiation-এ matrix গুণের ক্রম উল্টে ফেলা — matrix multiplication commutative না; base case (identity matrix) আর গুণের order ঠিক রাখো।
  6. Miller-Rabin-এ n − 1 = 2^s · d decompose করতে ভুল — d বিজোড় হওয়া পর্যন্ত 2 দিয়ে ভাগ; s গোনায় off-by-one মানেই ভুল রায়।
  7. Pollard rho-তে n prime কি না আগে check না করা — rho prime-এ অনন্ত ঘুরবে; আগে Miller-Rabin, তারপর rho।
  8. Segmented sieve-এ window-এর শুরু থেকে multiple-এর offset ভুল করা — max(p*p, ((L + p − 1) // p) * p) — এই ceiling-multiple হিসাবটা খাতায় একবার করে নাও।
  9. Python-এ এসব লাগবে না ভেবে sympy.isprime দিয়েই চালানো — শেখার সময় নিজে লেখো; contest-এ library allowed হলে তখন আলাদা কথা।

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

  • [ ] 14টা problem-ই অন্তত একবার নিজে solve করেছি
  • [ ] gcd(30, 18)-এর extended Euclid টা না দেখে খাতায় নামাতে পারি (x, y সহ)
  • [ ] একটা CRT উদাহরণ (যেমন x ≡ 2 mod 3, x ≡ 3 mod 5) হাতে মিলিয়েছি
  • [ ] μ(1) থেকে μ(12) পর্যন্ত table টা যুক্তিসহ বানিয়েছি
  • [ ] Fibonacci matrix-এর এক ধাপ গুণ হাতে করে F(2), F(3) মিলিয়েছি
  • [ ] Miller-Rabin একটা composite-এ (যেমন 561 — Carmichael number!) চালিয়ে দেখেছি
  • [ ] SPF array দিয়ে 60-এর factorization O(log n)-এ trace করেছি

সব টিক দিতে পারলে — চলো Level 11: Hard Mixed CP Patterns-এ। (আর interview-পথের পথিক হলে — মূল DS topic গুলো শেষ; এখানে যা শিখলে তা bonus মশলা।)

Source map

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