# 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](../../../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](../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](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](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](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](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](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](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](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](132-fibonacci-matrix-expo.md) | নোট আছে |
| 133 | Fast Doubling Fibonacci | Hard | F(2k) formulas | 132 | CP-Algorithms Fibonacci page | [133-fast-doubling-fibonacci.md](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](134-primality-test-advanced.md) | নোট আছে |
| 135 | Miller-Rabin Intro | Hard | probabilistic test | 134, 029 | CP-Algorithms primality tests page | [135-miller-rabin-intro.md](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](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](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](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 — শৃঙ্খল ভাঙলে পরেরটা ঝুলে যায়।

```text
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](../concept-notes.md)। ছবি এঁকে বুঝতে চাইলে → [../visualization-ideas.md](../visualization-ideas.md)।