Здравствуйте, дорогие друзья! Спасибо, что читаете мой канал! Вы когда-нибудь слышали о факториале? Сегодня расскажу Вам, что это такое и для чего он нужен. Факториал - это математическая функция, применяемая к неотрицательным целым числам, равная произведению всех натуральных чисел от 1 до числа, для которого она вычисляется (о целых, натуральных и других числах можно почитать здесь). Обозначается она очень просто: n! (произносится "эн факториал") - да, просто приписывается восклицательный знак к числу :) Чтобы было легче понять определение факториала, сразу приведу пример: 5!=1х2х3х4х5=120...

Статья подготовлена для студентов курса «Алгоритмы для разработчиков» в образовательном проекте OTUS. Рассмотрим задачу вычисления формул, состоящих из дробей, где в числителе и в знаменателе присутствуют факториалы (например, биномиальные коэффициенты). Будем вычислять факториалы по некоторому небольшому простому модулю p, пропуская сами множители p, потому что в дробях множители p сократятся, и результат будет взят по модулю p. Видно, что формула делится на несколько блоков одинаковой длины,...