Skip to content

Problems — Level 10: Advanced Number Theory

এই folder-এ Level 10-এর 14টা problem-এর note থাকবে। মনে করিয়ে দিই: এই level interview-এর জন্য optional, CP-র জন্য deep — তাড়াহুড়ো নেই, DS topic গুলো (02-13) শেষ করেও ফেরা যায়। প্রতিটা problem-এর জন্য আলাদা .md file — নিজের ভাষায় বোঝা, intuition, dry run, code, আর ভুল থেকে শেখা।

কীভাবে problem গুলো use করবে?

প্রতিটা problem-এর note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর একটা template, problem বোঝা থেকে brute force → optimization → dry run → complexity পর্যন্ত। এই level-এর বিশেষ অভ্যাস: প্রতিটা algorithm-এ অন্তত একটা হাতে-করা সংখ্যার উদাহরণ (যেমন gcd(99, 78)-এর পুরো back-substitution) note-এ রাখো — advanced topic-এ হাতের হিসাবই বোঝার একমাত্র প্রমাণ।

নিয়মটা সহজ:

  1. Table থেকে একটা problem নাও (recommended order ../README.md-তে আছে — trilogy গুলো ভেঙো না!)
  2. সংশ্লিষ্ট CP-Algorithms page-টা একবার চোখ বুলাও, তারপর না দেখে নিজে implement করার চেষ্টা — অন্তত 30-40 মিনিট
  3. তারপর note file বানাও/পড়ো, নিজের approach-এর সাথে মেলাও
  4. Solve হয়ে গেলে Status planned থেকে done করে দাও

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
125 Extended Euclidean Algorithm Medium back substitution 018, 019 CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html 125-extended-euclidean.md planned
126 Linear Diophantine Equation Medium gcd divisibility 125 CP-Algorithms — https://cp-algorithms.com/algebra/linear-diophantine-equation.html 126-linear-diophantine.md planned
127 Chinese Remainder Theorem Basic Hard modulus merge 125 CP-Algorithms — https://cp-algorithms.com/algebra/chinese-remainder-theorem.html 127-crt-basic.md planned
128 Euler Totient Advanced Medium multiplicative phi 023 CP-Algorithms — https://cp-algorithms.com/algebra/phi-function.html 128-euler-totient-advanced.md planned
129 Mobius Function Intro Hard IE encoding 044, 128 Wikipedia — https://en.wikipedia.org/wiki/M%C3%B6bius_function 129-mobius-function-intro.md planned
130 Modular Inverse Advanced Medium ext-gcd inverse 125, 032 CP-Algorithms — https://cp-algorithms.com/algebra/module-inverse.html 130-modular-inverse-advanced.md planned
131 Matrix Exponentiation Hard recurrence as matrix 029 Classic CP technique (USACO Guide — https://usaco.guide/) 131-matrix-exponentiation.md planned
132 Fibonacci using Matrix Exponentiation Hard matrix power 131 CP-Algorithms Fibonacci — https://cp-algorithms.com/algebra/fibonacci-numbers.html 132-fibonacci-matrix-expo.md planned
133 Fast Doubling Fibonacci Hard F(2k) formulas 132 CP-Algorithms Fibonacci page 133-fast-doubling-fibonacci.md planned
134 Primality Test Advanced Medium beyond trial division 013 CP-Algorithms — https://cp-algorithms.com/algebra/primality_tests.html 134-primality-test-advanced.md planned
135 Miller-Rabin Intro Hard probabilistic test 134, 029 CP-Algorithms primality tests page 135-miller-rabin-intro.md planned
136 Pollard Rho Intro Hard cycle factoring 135 CP-Algorithms — https://cp-algorithms.com/algebra/factorization.html 136-pollard-rho-intro.md planned
137 Sieve Variants Medium SPF / linear sieve 015 CP-Algorithms — https://cp-algorithms.com/algebra/prime-sieve-linear.html 137-sieve-variants.md planned
138 Segmented Sieve Hard windowed sieve 137 CP-Algorithms sieve page — https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html 138-segmented-sieve.md planned

"Inherits from" column-টা কী?

এই level-এর শিকড় সব level 1-2-তে — 125 দাঁড়িয়ে gcd-র (018, 019) উপর, 131 দাঁড়িয়ে binary exponentiation-এর (029) উপর, 137 দাঁড়িয়ে basic sieve-এর (015) উপর। আর level-এর ভেতরেই তিনটা trilogy — শৃঙ্খল ভাঙলে পরেরটা ঝুলে যায়।

018, 019 [gcd] ──▶ 125 (ext Euclid) ──┬──▶ 126 (Diophantine)
                                      ├──▶ 127 (CRT)
                                      └──▶ 130 (inverse) ◀── 032 [Fermat]
023 [totient] ──▶ 128 (phi advanced) ──▶ 129 (Mobius) ◀── 044 [IE]
029 [binary expo] ──▶ 131 (matrix expo) ──▶ 132 (Fibonacci) ──▶ 133 (fast doubling)
013 [trial division] ──▶ 134 ──▶ 135 (Miller-Rabin) ──▶ 136 (Pollard rho)
015 [sieve] ──▶ 137 (variants) ──▶ 138 (segmented)

একটা ছোট পরামর্শ

এই level-এ "বুঝেছি মনে হচ্ছে" আর "implement করতে পারি" — দুটোর ফাঁক সবচেয়ে বড়। CP-Algorithms পড়ে মাথা নাড়ানো সহজ; খালি editor-এ ext_gcd-এর update rule নির্ভুল লেখা কঠিন। তাই নিয়ম করো: প্রতিটা algorithm পরপর দুদিন না দেখে লিখবে — দ্বিতীয় দিনে আটকালে মানে প্রথম দিনের বোঝাটা ধার করা ছিল। আর Python-এর built-in pow(a, -1, m) (inverse) বা math.gcd — শেখার পর্বে নিষিদ্ধ, শেখা শেষে পুরস্কার।

Concept ঝালাই করতে হলে → ../concept-notes.md। ছবি এঁকে বুঝতে চাইলে → ../visualization-ideas.md।