Корневая декомпозиция: различия между версиями

Текущая версия на 13:45, 11 января 2020

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

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

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

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

@@ Строка 1: / Строка 1: @@
 Иногда в задаче возникают ситуации, когда мы умеем решать ее когда какое-то свойство < $\sqrt{N}$ и больше $\sqrt{N}$. Данный подход и называется корневой декомпозицией(оптимизацией).
-Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A * B <= N$, то одно из чисел < $\sqrt{N}$.
+Самыми простыми и наиболее известными применениями данной оптимизации являются : алгоритм проверки на простоту чисел(рассмотрим делители < $\sqrt{N}$ и больше, но так как для любого делителя больше корня можно найти делитель меньше корня => нам надо честно рассмотреть только первые) и например факт, что если суммарная длина строк = $N$, то различных длин строк будет не более $\sqrt{N}$ или если вы увидели ограничение $A B \le N$, то одно из чисел < $\sqrt{N}$.
 {{Автор|Глеб Лобанов|glebodin}}
 [[Категория:Конспект]]