কনটেন্টে যান

Problems — Level 10: Advanced Number Theory

এই folder-এ Level 10-এর 14টা problem-এর নোট আছে। মনে করিয়ে দিই: এই 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. তারপর বিদ্যমান নোট পড়ো, নিজের approach-এর সাথে মেলাও
  4. নিজের অগ্রগতি আলাদা করে চিহ্নিত করো; “নোট আছে” মানে এই সাইটে ব্যাখ্যা আছে, তুমি সমাধান করেছ—এমন দাবি নয়।

Tracker table

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

"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।