Корневая декомпозиция

Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией).

Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A * B <= N$, то одно из чисел < $\sqrt{N}$.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin