Как вычислить обратное число факториалу

peltorator

Часто бывает так, что в задаче нужно делить по модулю много раз. Это можно делать обычным алгоритмом взятия обратного по модулю за $O(\log p)$ на запрос. Если мы сделаем $n$ запросов, то асимптотика будет $O(n \log p)$. Сейчас мы рассмотрим алгоритм, который изначально предпосчитает обратные ко всем остаткам за $O(p)$, и тогда на запросы мы будем отвечать за $O(1)$. Если $n$ порядка $p$ или больше, то этот вариант будет более эффективен.

Есть много разных алгоритмов, которые делают это. Здесь будут представлены два, пожалуй, самых простых: один очень простой в понимании и написании, а другой еще легче в написании, однако не настолько очевидный с точки зрения понимания и придумывания.

Метод обратных факториалов

Идея первого алгоритма заключается в том, что мы посчитаем все возможные факториалы и обратные факториалы, а любое обратное к какому-то остатку представим как отношение двух факториалов.

Теорема: Теорема Вильсона гласит, что если $p$ — простое число, то

$$ (p — 1)! \equiv -1 \pmod p $$

Доказательство:

Давайте заметим, что все остатки от $1$ до $p — 1$ разбиваются на пары вида $x$, $x^<-1>$. Произведение чисел в паре равно единице по модулю $p$. Есть один крайний случай: когда $x = x^<-1>$. Это происходит в том случае, если $x^2 \equiv 1 \pmod p$, то есть $x^2 — 1 = (x — 1) \cdot (x + 1)\ ⋮\ p$. Значит, $x \equiv \pm 1 \pmod p$. Тогда в итоге $(p — 1)!$ по модулю $p$ состоит из произведения нескольких единиц, а также одной $-1$. Так что $(p — 1)! \equiv -1 \pmod p$. Что и требовалось доказать.

Зная этот факт, мы можем сразу понять, что $\left((p — 1)!\right)^ <-1>\equiv -1 \pmod p$, потому что обратное к $-1$ — это $-1$. Таким образом, обратное к $(p — 1)!$ мы уже посчитали.

Замечание: На самом деле не обязательно было пользоваться этой формулой. Можно было посчитать за $O(p)$ число $(p — 1)!$, а потом бинарным возведением в степень найти к нему обратное за $O(\log p)$. Итоговая асимптотика бы от этого не пострадала.

Мы уже нашли обратное к $(p — 1)!$. Как же найти обратное к $(p — 2)!$ теперь? Заметим следующий факт:

Так что алгоритм нахождения всех обратных факториалов следующий: идем с конца, изначально устанавливаем, что обратное к $(p — 1)!$ — это $-1$, а затем пересчитываем по очереди обратное к $k!$ как обратное к $(k + 1)!$, умноженное на $k + 1$.

Теперь пусть мы посчитали все факториалы и все обратные факториалы за $O(p)$. Как найти обратные ко всем остаткам? С этим нам поможет следующая формула:

А отношение двух факториалов — это произведение первого факториала на обратное ко второму.

Представим код алгоритма:

Весь алгоритм — это два прохода по числам от $1$ до $p — 1$, так что работает он за $O(p)$. Потребление памяти тоже $O(p)$, потому что нужно хранить массивы факториалов и обратных факториалов. От одного из них можно избавиться, если вычислять ответ на лету (в приведенном коде мы не хранили факториалы), однако не от обоих.

Упражнение: Придумайте модернизацию этого алгоритма, которая работает за $O(p)$, но при этом потребляет $O(\sqrt

)$ памяти (считайте, что ответы — вектор inverses — вы можете просто выводить на экран, и вам не нужно их хранить).

Замечание: Заметим, что можно считать обратные факториалы, начиная не обязательно с $p — 1$. Если нам нужно найти обратные ко всем остаткам от $1$ до $n$, то можно за $O(n)$ посчитать $n! \bmod p$, найти к нему обратное за $O(\log p)$ и потом аналогично представленному выше способу насчитать все обратные факториалы от $1$ до $n$. Тогда подсчет обратных ко всем остаткам от $1$ до $n$ будет работать за $O(n + \log p)$.

Как вы можете видеть, алгоритм очень простой. Однако его редко получится где-то применить, потому что, во-первых, нахождение всех обратных по отдельности работает за $O(p \log p)$, что тяжело отсечь от $O(p)$ на неучебной задаче, а во-вторых, модуль чаще всего — это число порядка $10^9$, поэтому вы не имеете возможности посчитать обратные ко всем остаткам, и использование стандартного алгоритма за $O(n \log p)$ дает более эффективное решение.

Алгоритм одного цикла

Второй алгоритм пишется всего одним циклом. Однако чтобы его вспомнить, придется написать пару формул на бумажке.

Алгоритм основывается на одном простом факте:

Теорема: $$ \frac<1> \equiv -\left\lfloor \frac

\right\rfloor \cdot \frac<1>

\pmod p $$

Доказательство: Давайте представим $p$ в виде $k \cdot x + y$, где $x = \left\lfloor \frac

\right\rfloor$ и $y = p \bmod k$.

Необходимо проверить, что

$$k \cdot \left(-\left\lfloor \frac

\right\rfloor \cdot \frac<1>

\right) \equiv 1 \pmod p$$

$$ k \cdot (-x \cdot \frac<1>) = — (k \cdot x) \cdot \frac<1> = — \left((k \cdot x + y) — y\right) \cdot \frac<1> = — (p — y) \cdot \frac<1> \equiv y \cdot \frac<1> \equiv 1 \pmod p $$

Что и требовалось доказать.

Таким образом, мы можем посчитать обратное к $k$, если уже посчитано обратное к $p \bmod k$. Заметим, что это число меньше, чем $k$, поэтому все обратные можно вычислять по порядку.

Реализация у этого алгоритма крайне проста:

Также преимуществом этого метода является то, что это просто один цикл for по возрастанию, поэтому можно считать обратные не ко всем остаткам, а к первым $n$ остаткам за $O(n)$ очень легко. Однако не очень ясно, для чего это может вам понадобиться.

При тестировании на $p$ порядка $10^8$ второй алгоритм работает примерно в два раза быстрее, чем первый.

Обратный факториал

Обратный факториал числа N = n! (обозначение: n!? или N?) определяется как число, факториал которого n! и есть исходное число. Название обратный факториал аналогично названию обратная функция, ом. Большой англо-русский и русско-английский словарь мат. inverse factorial

В частности, n!? — это число предметов, количество перестановок которых (способов расположения) равно n!. Мнемоническое правило: обозначение обратный факториал «съедает» обозначение факториал.

Обратный факториал можно вычислить с помощью последовательного деления исходного числа на натуральные числа, пока не получим результат (число, равное очередному делителю):

или число, меньшее очередного делителя. В последнем случае дробная часть числа, инфолиофакториал которого равен исходному любому положительному числу, определяется решением квадратного уравнения от инфолиофакториала числа х, значения х! которого при целых х=n, совпадают с факториалом, а для всех иных значений х отличаются от значений Гамма-функции Г(х), предложенной Эйлером, http://ru.wikipedia.org/wiki/Гамма-функция.

Расширением понятия обратный факториал на любые, превосходящие единицу, положительные числа, является Инфолиократная функция

&nbsp Обратный факториал применяется при решении задач Шаблон:Изолированная статья

Что такое факториал и как его вычислить

Статья, после которой вы начнёте щёлкать факториалы как орешки.

Иллюстрация: Катя Павловская для Skillbox Media

Даже если вы уже давно окончили школу, факториалы всё равно могут доставить немало приятных флешбэков — например, если вы обучаетесь программированию и знакомитесь с задачками на рекурсию или комбинаторику. Поэтому мы решили максимально просто объяснить, что такое факториал, как его вычислять и зачем он вообще нужен.

Эта статья будет полезна как опытным программистам, которые хотят освежить знания, так и тем, кто ещё учится: школьникам, студентам и совсем зелёным джунам.

Что такое факториал

Факториал числа n — это произведение всех натуральных чисел от единицы до n. Обозначается факториал символом восклицательного знака: !.

Это определение из учебника, и оно пока звучит сложновато — неясно, зачем эти факториалы вообще нужны и как они могут пригодиться в науке и технике. Но об этом чуть позже — для начала давайте посмотрим на примеры факториалов:

Чтобы вычислить их, нам нужно перемножить все числа от единицы до числа, стоящего под знаком факториала — так гласит определение. Получаем выражения:

Ещё в математическом определении сказано, что факториал не может быть отрицательным или дробным — то есть вот такие факториалы вычислить нельзя:

Для чего нужен факториал

Факториалы незаменимы там, где нужно быстро посчитать количество комбинаций и сочетаний разных предметов. В математике этому посвящён даже целый раздел — комбинаторика. Её методы используют много где: от лингвистики до криптографии и анализа ДНК. И во всех этих сферах факториал помогает упрощать сложные вычисления.

Разберём на примере, как это работает.

Допустим, у вас есть пять шоколадок и вы решили раздать их пяти друзьям — каждому по одной. Задача — выяснить, сколько существует способов раздать эти шоколадки. Начинаем размышлять:

• первую шоколадку можно отдать одному из пяти друзей;
• вторую — одному из четырёх друзей, потому что один уже получил свою шоколадку;
• третью — одному из трёх, потому что двое уже наслаждаются своими шоколадками;
• четвёртую — одному из двух;
• пятую — последнему другу.

Получается, что способов раздать первую шоколадку — 5, вторую — 4, третью — 3, четвёртую — 2, а пятую — всего 1. По правилам математики, чтобы выяснить общее количество всех вариантов, нужно перемножить их между собой. Ну а кто мы такие, чтобы с этими правилами спорить?

Смотрим на выражение выше и понимаем: ведь оно идеально вписывается в определение факториала — произведение натуральных чисел от одного до n (в нашем случае n равно 5). Следовательно, это выражение можно коротко и изящно записать в виде факториала:

Выходит, что всего способов раздать пять шоколадок пяти друзьям существует 120. Вот как может выглядеть один из них:

Конечно, в жизни вам вряд ли придётся считать количество способов раздать друзьям шоколадки. Но, например, в статистике, теории вероятностей, матанализе и программировании факториалы используют сплошь и рядом. Так что, если видите себя в будущем на матмехе или, на худой конец, в IT, то лучше познакомиться с ними хотя бы бегло.

Какие свойства и формулы есть у факториалов

Так как факториалы используются в разных областях математики, свойств у них довольно много — каждая область привносит какие-то свои методы вычислений. Одно из свойств вы уже знаете: факториал — это всегда целое положительное число. Вот ещё несколько, которые стоит запомнить:

• Факториал нуля равен единице — 0! = 1.
• Факториал единицы тоже равен единице: 1! = 1.
• Рекурсия: n! = (n – 1)! × n. Это основное свойство факториалов, о нём мы чуть подробнее поговорим дальше.

Мы видим, что каждое свойство описывается какой-то формулой — и некоторые из этих формул могут быть весьма полезны. Они позволяют нам находить факториалы проще и быстрее, чем простым перемножением натуральных чисел. Разберём эти формулы тоже.

Формула Стирлинга

Чтобы вычислить факториал, не используя так много операций умножения, придумали формулу Стирлинга. Вот как она выглядит:

Выглядит страшно, но на самом деле она очень полезная. Её используют, когда хотят приблизительно узнать факториал большого числа. Обычным способом это будет сделать сложно даже мощному компьютеру — например, попробуйте посчитать в онлайн-калькуляторе факториал числа 10 024 (спойлер: это может занять несколько часов и даже дней).

Давайте попробуем вычислить факториал числа 6 по этой формуле:

Число e примерно равно 2,71, а π — 3,14. Подставляем их в выражение и получаем ответ:

Получили приближённое значение настоящего факториала, который равен 720. Но можно сделать ответ и более точным. Для этого нужно добавить больше знаков после запятой всем переменным — например, если взять 20 знаков, то ответ будет таким:

Это уже больше похоже на правду. Хотя погрешность всё равно есть.

Рекуррентная формула

Рекуррентная формула позволяет вычислить факториал числа n, основываясь на факториале предыдущего числа — (n – 1). Выглядит она так:

В целом рекуррентная формула не приносит нам большой пользы, так как всё равно приходится вычислять факториал предыдущего числа. Если он равен какому-то большому числу (например, 100), то использование формулы теряет смысл — слишком уж много вычислений это потребует.

Рекуррентная формула основана на главном свойстве факториалов — рекурсии: n! = (n – 1)! × n. Это свойство особенно полезно при решении задач по комбинаторике: так мы можем быстро сокращать факториалы и упрощать выражения.

Однако рекуррентная формула хорошо подходит для алгоритмов — в частности, для программирования. Мы можем задать начальное значение: например, что 0! = 1 или 1! = 1, а затем считать следующие факториалы по формуле:

Получим алгоритм для вычисления факториалов. Не очень эффективный, но простой.

Давайте вычислим по этой формуле факториал числа 4. Сначала распишем рекуррентную формулу до базового значения — факториала числа 1:

Можно записать это и в сокращённом виде:

Теперь последовательно подставляем значение факториала, которое мы уже знаем, и вычисляем результат:

Получили ответ — 24. Ничего сложного, просто перемножаем числа.

Кстати, всю эту формулу можно обернуть в реально работающую функцию на языке Python:

Можете попробовать запустить её в онлайн-интерпретаторе и посмотреть, как работает. Тут есть один нюанс: Python не даст вам посчитать факториал числа больше 998, так как у него есть ограничение на количество вызовов функции — в программировании это называется глубиной рекурсии.

Шпаргалка: таблица факториалов

Чтобы быстро находить, чему равен факториал, можно запомнить или сохранить в заметки вот такую табличку. Она рассчитана всего на 12 чисел, но для большинства учебных задач этого хватит.

1!	1
2!	2
3!	6
4!	24
5!	120
6!	720
7!	5040
8!	40 320
9!	362 880
10!	3 628 800
11!	39 916 800
12!	479 001 600

Примеры задач на факториалы с решениями

С теорией вроде разобрались — теперь попробуем решить несколько задач с факториалами, чтобы закрепить знания на практике.

Умножение факториалов

Задача: перемножить два факториала.

Решение:

Сперва нужно вычислить значения факториалов, а затем перемножить полученные значения:

Обратите внимание: во второй строке мы применили рекуррентную формулу, чтобы быстрее вычислить факториал числа 7.

Вычитание факториалов

Задача: вычесть из одного факториала другой.

Решение:

Используем тот же подход, что и в предыдущей задаче: сначала вычисляем факториалы, а затем получаем ответ на всё выражение.

Вроде бы ничего сложного, главное — не запутаться в умножении.

Перемножение факториалов

Задача: умножить один факториал на другой:

Решение:

Вычисляем факториалы, потом перемножаем их значения:

Во второй строке мы воспользовались таблицей выше и быстро нашли значение факториала от числа 8.

Сокращение факториалов

Задача: сократить дробь и вычислить её значение.

Решение:

Здесь мы воспользуемся рекуррентной формулой для вычисления факториала и разложим верхний факториал на множители:

В первой строке мы применили рекуррентную формулу два раза, а во второй — просто сократили одинаковые факториалы в числителе и в знаменателе.

Разложение факториалов

Задача: сократить дробь.

Решение:

Хотя здесь нет конкретных чисел, но принцип решения остаётся таким же: используем рекуррентную формулу и сокращаем одинаковые значения в числителе и знаменателе.

Главное — не запутаться и правильно применить рекуррентную формулу.

Что запомнить

• Факториал — это произведение всех натуральных чисел от 1 до данного числа. Например, факториал числа 5 будет равен 1 × 2 × 3 × 4 × 5 = 120.
• Его используют во многих областях науки — например, комбинаторике, теории вероятностей и математическом анализе.
• Помимо стандартной формулы для вычисления факториала можно использовать формулы Стирлинга и рекуррентную формулу.
• Формула Стирлинга нужна для того, чтобы посчитать факториал без большого числа операций умножения.
• Рекуррентная формула позволяет вычислить факториал на основе предыдущего факториала.

Читайте также:

Натуральные числа — это числа, которыми мы считаем количество предметов. Например, 1, 2, 5, 20, 43. Натуральные числа не могут быть отрицательными, а также дробными — только положительными и целыми. Минимальное натуральное число — ноль, а максимальное — бесконечность.

Профессия Data Scientist

Освойте Data Science с нуля. Вы попробуете силы в аналитике данных, машинном обучении, дата-инженерии и подробно изучите направление, которое нравится вам больше. Отточите навыки на реальных проектах и станете востребованным специалистом.

Узнать про курс

Профессии с трудоустройством

• Графический дизайнер
• Python-программист
• Инженер по тестированию
• Бизнес-аналитик
• Интернет-маркетолог 2023

Новости

+7 (499) 444-90-36 Отдел заботы о пользователях

Москва, Ленинский проспект, дом 6, строение 20

• Премии Рунета 2018, 2019, 2020

• Все направления

• О Skillbox

• Вебинары

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies ��

Обратный элемент по модулю

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(10^9 + 7\) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: \(\frac<8> <2>= 4\) , но \(\frac<8 \% 5 = 3> <2 \% 5 = 2>\neq 4\) .

Способ 1: бинарное возведение в степень

Если модуль \(p\) простой, то решением будет \(a^ <-1>\equiv a^\) . Это следует из малой теоремы Ферма:

Теорема. \(a^p \equiv a \pmod p\) для всех \(a\) , не делящихся на \(p\) .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь \(P(x_1, x_2, \ldots, x_n) = \frac<\prod (x_i!)>\) это мультиномиальный коеффициент — количество раз, которое элемент \(a_1^ a_2^ \ldots a_n^\) появится при раскрытии скобки \((a_1 + a_2 + \ldots + a_n)^k\) .

Теперь два раза «поделим» наш результат на \(a\) .

\[ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ <-1>\]

Получается, что \(a^\) ведет себя как \(a^<-1>\) , что нам по сути и нужно. Посчитать \(a^\) можно за \(O(\log p)\) бинарным возведением в степень.

Приведем код, который позволяет считает \(C_n^k\) .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть \(a\) и \(b\) известны, и нужно найти такие целые (возможно, отрицательные) \(x\) и \(y\) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве \(a\) и \(b\) соответственно \(a\) и \(m\)

Одним из решений уравнения и будет \(a^<-1>\) , потому что если взять уравнение по модулю \(m\) , то получим

\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ <-1>\pmod m \]

Преимущества этого метода над возведением в степень:

• Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
• Алгоритм проще выполнять руками.

Сам автор почти всегда использует возведение в степень.

Почему \(10^9+7\) ?

1. Это выражение довольно легко вбивать ( 1e9+7 ).
2. Простое число.
3. Достаточно большое.
4. int не переполняется при сложении.
5. long long не переполняется при умножении.

Кстати, \(10^9 + 9\) обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же \(C_n^k\) , но для больших \(n\) и \(k\) , поэтому асимптотика \(O(n \log m)\) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить \(O(\log m)\) операций, посчитав \(m!^<-1>\) .

Обратный элемент по модулю

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(10^9 + 7\) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: \(\frac<8> <2>= 4\) , но \(\frac<8 \% 5 = 3> <2 \% 5 = 2>\neq 4\) .

Способ 1: бинарное возведение в степень

Если модуль \(p\) простой, то решением будет \(a^ <-1>\equiv a^\) . Это следует из малой теоремы Ферма:

Теорема. \(a^p \equiv a \pmod p\) для всех \(a\) , не делящихся на \(p\) .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь \(P(x_1, x_2, \ldots, x_n) = \frac<\prod (x_i!)>\) это мультиномиальный коеффициент — количество раз, которое элемент \(a_1^ a_2^ \ldots a_n^\) появится при раскрытии скобки \((a_1 + a_2 + \ldots + a_n)^k\) .

Теперь два раза «поделим» наш результат на \(a\) .

\[ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ <-1>\]

Получается, что \(a^\) ведет себя как \(a^<-1>\) , что нам по сути и нужно. Посчитать \(a^\) можно за \(O(\log p)\) бинарным возведением в степень.

Приведем код, который позволяет считает \(C_n^k\) .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть \(a\) и \(b\) известны, и нужно найти такие целые (возможно, отрицательные) \(x\) и \(y\) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве \(a\) и \(b\) соответственно \(a\) и \(m\)

Одним из решений уравнения и будет \(a^<-1>\) , потому что если взять уравнение по модулю \(m\) , то получим

\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ <-1>\pmod m \]

Преимущества этого метода над возведением в степень:

• Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
• Алгоритм проще выполнять руками.

Сам автор почти всегда использует возведение в степень.

Почему \(10^9+7\) ?

1. Это выражение довольно легко вбивать ( 1e9+7 ).
2. Простое число.
3. Достаточно большое.
4. int не переполняется при сложении.
5. long long не переполняется при умножении.

Кстати, \(10^9 + 9\) обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же \(C_n^k\) , но для больших \(n\) и \(k\) , поэтому асимптотика \(O(n \log m)\) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить \(O(\log m)\) операций, посчитав \(m!^<-1>\) .

Как вычислить число обратное по модулю

Часто в задачах требуется посчитать что-то по простому модулю (чаще всего \(10^9 + 7\) ). Это делают для того, чтобы участникам не приходилось использовать длинную арифметику, и они могли сосредоточиться на самой задаче.

Обычные арифметические операции выполняются не сильно сложнее — просто нужно брать модули и заботиться о переполнении. Например:

Но вот с делением возникают проблемы — мы не можем просто взять и поделить. Пример: \(\frac = 4\) , но \(\frac \neq 4\) .

Способ 1: бинарное возведение в степень

Если модуль \(p\) простой, то решением будет \(a^ \equiv a^

\) . Это следует из малой теоремы Ферма:

Теорема. \(a^p \equiv a \pmod p\) для всех \(a\) , не делящихся на \(p\) .

Доказательство. (для понимания несущественно, можно пропустить)

Здесь \(P(x_1, x_2, \ldots, x_n) = \frac \) это мультиномиальный коеффициент — количество раз, которое элемент \(a_1^ a_2^ \ldots a_n^ \) появится при раскрытии скобки \((a_1 + a_2 + \ldots + a_n)^k\) .

Теперь два раза «поделим» наш результат на \(a\) .

\[ a^p \equiv a \implies a^

\equiv 1 \implies a^

Получается, что \(a^

\) ведет себя как \(a^ \) , что нам по сути и нужно. Посчитать \(a^

\) можно за \(O(\log p)\) бинарным возведением в степень.

Приведем код, который позволяет считает \(C_n^k\) .

Способ 2: диофантово уравнение

Диофантовыми уравнениями называют такие штуки:

Требуется решить их в целых числах, то есть \(a\) и \(b\) известны, и нужно найти такие целые (возможно, отрицательные) \(x\) и \(y\) , чтобы равенство выполнялось. Решают такие вещи расширенным алгоритмом Евклида. TODO: описать, как он работает.

Подставим в качестве \(a\) и \(b\) соответственно \(a\) и \(m\)

Одним из решений уравнения и будет \(a^ \) , потому что если взять уравнение по модулю \(m\) , то получим

\[ ax + by = 1 \iff ax \equiv 1 \iff x \equiv a^ \pmod m \]

Преимущества этого метода над возведением в степень:

• Если обратное существует, то оно найдется даже если модуль не простой. Способ с бинарным возведением тоже можно заставить работать с произвольным модулем, но это будет намного труднее.
• Алгоритм проще выполнять руками.

Сам автор почти всегда использует возведение в степень.

Почему \(10^9+7\) ?

1. Это выражение довольно легко вбивать ( 1e9+7 ).
2. Простое число.
3. Достаточно большое.
4. int не переполняется при сложении.
5. long long не переполняется при умножении.

Кстати, \(10^9 + 9\) обладает теми же свойствами. Иногда используют и его.

Предподсчёт обратных факториалов за линейное время

Пусть нам нужно зачем-то посчитать все те же \(C_n^k\) , но для больших \(n\) и \(k\) , поэтому асимптотика \(O(n \log m)\) нас не устроит. Оказывается, мы можем сразу предподсчитать все обратные ко всем факториалам.

Если у нас уже написан inv , то нам не жалко потратить \(O(\log m)\) операций, посчитав \(m!^ \) .

Как вычислить обратный элемент по модулю [дубликат]

В общем случае ответ @MBo про расширенный алгоритм Евклида работает в большом классе колец, так называемых Евклидовых кольцах. Например, в кольцах многочленов над полями.

Но в частном случае циклических групп, когда известно разложение порядка группы на множители, можно пользоваться теоремой Эйлера. В вашем случае 4^10 == 1 (mod 11) , следовательно 4^(-1) == 4^9 (mod 11) == 3 (mod 11) .

Чуть более обще. Пусть n — модуль, phi(n) — функция Эйлера для n , тогда a^(-1) == a^(phi(n)-1) (mod n) .

Обратный по модулю в кольце

Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.

Использование:

Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.

Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».

Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.

Ограничения:

Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.

Что значит по модулю?

Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.

Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.

Что такое обратное?

Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:

Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5).
Все действительные числа, кроме 0, имеют обратную
Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)

Что такое обратное по модулю?

В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.

Модульная инверсия a (mod m) есть a -1
(a * a -1 ) ≡ 1 (mod m) или эквивалентно (a * a -1 ) mod m = 1
Только числа, взаимно простые с модулем m, имеют модульное обратное.

Говоря проще, обратным элементом к a по модулю m является такое число b, что остаток от деления (a * b) на модуль m равно единице (a * a -1 ) mod m = 1

Как найти модульный обратный

Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1

Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.

Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.

Расширенный алгоритм Евклида

Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.

Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).

Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.

Алгоритм:

Выход : d, x, y, такие что d = gcd(a, m) = ax + my

3. [Выход] Вернуть (d, x, y) = (a₀, x₀, y₀)

Битовая сложность расширенного алгоритма Евклида равна O((log₂(n)) 2 ) , где n = max (|a|, |m|)

Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.

Пример для наивного метода.

Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.

Шаг 1 . Рассчитать a * b mod m для значений B от 0 до m-1. По очереди проверяем числа от 0 до 6.

3 * 0 ≡ 0 (mod 7) — не подходит
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <—— Обратное найдено.
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

при b = 5 выполнилось условие, что a * b ≡ 1 (m). Следовательно, b = 5 является обратным элементом к 3 по модулю 7.

Пример на расширенный алгоритм Евклида.

Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.

Итерация	q	a0	a1	x0	x1	y0	y1
0	—	3	7	1	0	0	1
1	0	7	3	0	1	1	0
2	2	3	1	1	-2	0	1
3	3	1	0	-2	0	1	-3

После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.

(d, x, y) = (1, -2, 1), видим, что d = НОД(3, 7) = 1, следовательно числа 3 и 7 являются взаимно простыми, а значит обратный существует.

Делаем проверку:

3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!

Обратным элементом к тройке по модулю 7 является x = -2. По модулю 7 число -2 равно 5. Получили, что x = 5 является обратным элементом к 3 по модулю 7.

Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.

peltorator

Часто бывает так, что в задаче нужно делить по модулю много раз. Это можно делать обычным алгоритмом взятия обратного по модулю за $O(\log p)$ на запрос. Если мы сделаем $n$ запросов, то асимптотика будет $O(n \log p)$. Сейчас мы рассмотрим алгоритм, который изначально предпосчитает обратные ко всем остаткам за $O(p)$, и тогда на запросы мы будем отвечать за $O(1)$. Если $n$ порядка $p$ или больше, то этот вариант будет более эффективен.

Есть много разных алгоритмов, которые делают это. Здесь будут представлены два, пожалуй, самых простых: один очень простой в понимании и написании, а другой еще легче в написании, однако не настолько очевидный с точки зрения понимания и придумывания.

Метод обратных факториалов

Идея первого алгоритма заключается в том, что мы посчитаем все возможные факториалы и обратные факториалы, а любое обратное к какому-то остатку представим как отношение двух факториалов.

Теорема: Теорема Вильсона гласит, что если $p$ — простое число, то

$$ (p — 1)! \equiv -1 \pmod p $$

Доказательство:

Давайте заметим, что все остатки от $1$ до $p — 1$ разбиваются на пары вида $x$, $x^<-1>$. Произведение чисел в паре равно единице по модулю $p$. Есть один крайний случай: когда $x = x^<-1>$. Это происходит в том случае, если $x^2 \equiv 1 \pmod p$, то есть $x^2 — 1 = (x — 1) \cdot (x + 1)\ ⋮\ p$. Значит, $x \equiv \pm 1 \pmod p$. Тогда в итоге $(p — 1)!$ по модулю $p$ состоит из произведения нескольких единиц, а также одной $-1$. Так что $(p — 1)! \equiv -1 \pmod p$. Что и требовалось доказать.

Зная этот факт, мы можем сразу понять, что $\left((p — 1)!\right)^ <-1>\equiv -1 \pmod p$, потому что обратное к $-1$ — это $-1$. Таким образом, обратное к $(p — 1)!$ мы уже посчитали.

Замечание: На самом деле не обязательно было пользоваться этой формулой. Можно было посчитать за $O(p)$ число $(p — 1)!$, а потом бинарным возведением в степень найти к нему обратное за $O(\log p)$. Итоговая асимптотика бы от этого не пострадала.

Мы уже нашли обратное к $(p — 1)!$. Как же найти обратное к $(p — 2)!$ теперь? Заметим следующий факт:

Так что алгоритм нахождения всех обратных факториалов следующий: идем с конца, изначально устанавливаем, что обратное к $(p — 1)!$ — это $-1$, а затем пересчитываем по очереди обратное к $k!$ как обратное к $(k + 1)!$, умноженное на $k + 1$.

Теперь пусть мы посчитали все факториалы и все обратные факториалы за $O(p)$. Как найти обратные ко всем остаткам? С этим нам поможет следующая формула:

А отношение двух факториалов — это произведение первого факториала на обратное ко второму.

Представим код алгоритма:

Весь алгоритм — это два прохода по числам от $1$ до $p — 1$, так что работает он за $O(p)$. Потребление памяти тоже $O(p)$, потому что нужно хранить массивы факториалов и обратных факториалов. От одного из них можно избавиться, если вычислять ответ на лету (в приведенном коде мы не хранили факториалы), однако не от обоих.

Упражнение: Придумайте модернизацию этого алгоритма, которая работает за $O(p)$, но при этом потребляет $O(\sqrt

)$ памяти (считайте, что ответы — вектор inverses — вы можете просто выводить на экран, и вам не нужно их хранить).

Замечание: Заметим, что можно считать обратные факториалы, начиная не обязательно с $p — 1$. Если нам нужно найти обратные ко всем остаткам от $1$ до $n$, то можно за $O(n)$ посчитать $n! \bmod p$, найти к нему обратное за $O(\log p)$ и потом аналогично представленному выше способу насчитать все обратные факториалы от $1$ до $n$. Тогда подсчет обратных ко всем остаткам от $1$ до $n$ будет работать за $O(n + \log p)$.

Как вы можете видеть, алгоритм очень простой. Однако его редко получится где-то применить, потому что, во-первых, нахождение всех обратных по отдельности работает за $O(p \log p)$, что тяжело отсечь от $O(p)$ на неучебной задаче, а во-вторых, модуль чаще всего — это число порядка $10^9$, поэтому вы не имеете возможности посчитать обратные ко всем остаткам, и использование стандартного алгоритма за $O(n \log p)$ дает более эффективное решение.

Алгоритм одного цикла

Второй алгоритм пишется всего одним циклом. Однако чтобы его вспомнить, придется написать пару формул на бумажке.

Алгоритм основывается на одном простом факте:

Теорема: $$ \frac<1> \equiv -\left\lfloor \frac

\right\rfloor \cdot \frac<1>

\pmod p $$

Доказательство: Давайте представим $p$ в виде $k \cdot x + y$, где $x = \left\lfloor \frac

\right\rfloor$ и $y = p \bmod k$.

Необходимо проверить, что

$$k \cdot \left(-\left\lfloor \frac

\right\rfloor \cdot \frac<1>

\right) \equiv 1 \pmod p$$

$$ k \cdot (-x \cdot \frac<1>) = — (k \cdot x) \cdot \frac<1> = — \left((k \cdot x + y) — y\right) \cdot \frac<1> = — (p — y) \cdot \frac<1> \equiv y \cdot \frac<1> \equiv 1 \pmod p $$

Что и требовалось доказать.

Таким образом, мы можем посчитать обратное к $k$, если уже посчитано обратное к $p \bmod k$. Заметим, что это число меньше, чем $k$, поэтому все обратные можно вычислять по порядку.

Реализация у этого алгоритма крайне проста:

Также преимуществом этого метода является то, что это просто один цикл for по возрастанию, поэтому можно считать обратные не ко всем остаткам, а к первым $n$ остаткам за $O(n)$ очень легко. Однако не очень ясно, для чего это может вам понадобиться.

При тестировании на $p$ порядка $10^8$ второй алгоритм работает примерно в два раза быстрее, чем первый.

Обратный факториал

Обратный факториал числа N = n! (обозначение: n!?) определяется как число, факториал которого n! и есть исходное число. Название обратный факториал аналогично названию обратная функция, ом. Большой англо-русский и русско-английский словарь мат. inverse factorial

В частности, n!? — это число предметов, количество перестановок которых (способов расположения) равно n!

Обратный факториал можно вычислить с помощью последовательного деления исходного числа на натуральные числа, пока не получим единицу:

n!? = n! / 1 / 2 / 3. / (n − 1) = n

или число, меньшее очередного делителя. В последнем случае дробная часть числа, инфолиофакториал которого равен исходному любому положительному числу, определяется решением квадратного уравнения от инфолиофакториала числа х, значения х! которого при целых х=n, совпадают с факториалом, а для всех иных значений х отличаются от значений Гамма-функции Г(х), предложенной Эйлером.

Например, число вариантов построения полевых игроков команды (1-й капитан, 2-й вратарь, далее остальные игроки в любой последовательности) 362880, тогда число игроков в команде может быть определено следующим образом: так как 362880/1/2/3/4/5/6/7/8/9=1, то 9+капитан+вратарь=11.

Wikimedia Foundation . 2010 .

Полезное

Смотреть что такое «Обратный факториал» в других словарях:

Кольцо (математика) — У этого термина существуют и другие значения, см. Кольцо. В абстрактной алгебре кольцо  это один из наиболее часто встречающихся видов алгебраической структуры. Простейшими примерами колец являются алгебры чисел (целых, вещественных,… … Википедия

Полупрямое произведение — Полупрямое произведение  конструкция в теории групп, позволяющая строить новую группу по двум группам и , и действию группы на группе автоморфизмами. Полупрямое произведение групп и над … Википедия

\ — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэк слеш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэкслеш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Бэкслэш — Обратная косая черта (англ. backslash, по русски часто упоминается как «обратный слеш» или «бэкслеш») символ «», назван так, чтобы отличаться от прямой косой черты (англ. «slash», по русски «слеш», «прямой слеш», «/»). Обратная косая черта… … Википедия

Штрих (письмо) — У этого термина существуют и другие значения, см. Штрих. ′ Штрих (письмо) Пунктуация … Википедия

Глоссарий теории групп — Группа (математика) Теория групп … Википедия

Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… … Энциклопедия инвестора