❤️| буст? #math
🤩 Что это такое?
Основная теорема арифметики: любое натуральное число больше 1 можно единственным образом разложить на простые множители.
360 = 2³ · 3² · 5¹
Показатель степени вхождения простого числа p в число n
— это максимальная степень k, такая что pᵏ делит n. Обозначается v_p(n).
Для 360: v₂ = 3, v₃ = 2, v₅ = 1, v₇ = 0.
Формула Лежандра
— как найти v_p(n!) без раскрытия факториала:
v_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...
🤩 Что из этого следует?
Свойства показателя вхождения:
v_p(a·b) = v_p(a) + v_p(b) — при умножении степени складываются.
v_p(a/b) = v_p(a) − v_p(b) — при делении вычитаются.
v_p(aᵏ) = k · v_p(a) — при возведении в степень умножается.
Именно поэтому «на сколько нулей оканчивается число» = min(v₂, v₅): ноль даёт пара 2·5.
Формула Лежандра работает потому, что ⌊n/p⌋ считает числа, делящиеся на p, ⌊n/p²⌋ — добавляет те, что делятся на p² (у них на один множитель больше), и так далее.
🤩 Как это применяется?
Определение количества нулей в конце факториала, делимость и НОД/НОК через разложение, задачи на «сколькими способами», теория чисел и криптография (RSA стоит на свойствах простых чисел).
🤩 Пример задачи:
Найти: сколько нулей на конце числа
❤️
100! — ?
❤️
Решение:
Ноль даёт пара 2·5. Двоек всегда больше, поэтому считаем пятёрки:
v₅(100!) = ⌊100/5⌋ + ⌊100/25⌋ + ⌊100/125⌋ = 20 + 4 + 0 = 24
Ответ:
❤️
24 нуля.
