Обратный элемент по модулю через теорему Ферма
Безопасно делите по модулю
«Обратный элемент по модулю через теорему Ферма» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Деление не работает по модулю
Сложение, вычитание и умножение хорошо работают по модулю, а обычное деление — нет. Нельзя просто разделить число и взять остаток. ⚠️
Замените деление умножением
Решение — обратный элемент по модулю: деление на x заменяется умножением на обратный элемент x. Поэтому a / b по модулю m превращается в умножение a на обратный элемент b.
Что такое обратный элемент
Обратный элемент числа x — это число, которое при умножении на x по данному модулю даёт 1. В обычной арифметике он играет роль 1/x.
# x * inv(x) % m == 1Простые модули делают это возможным
Обратный элемент существует только тогда, когда x и m не имеют общих делителей. Простой модуль, например 1e9+7, гарантирует наличие обратного элемента для любого ненулевого x.
Теорема Ферма о малой теореме
Малая теорема Ферма утверждает, что для простого p число x в степени p минус 1 сравнимо с 1 по модулю p, если x не кратно p.
# x^(p-1) % p == 1Выведите обратный элемент
Вынесите один множитель x, и оставшаяся часть должна быть его обратным элементом. Поэтому обратный элемент x равен x в степени p минус 2, взятому по модулю p.
# inv(x) = x^(p-2) % pВычислите его быстрым возведением в степень
Этот показатель степени огромен, поэтому используйте быстрое возведение в степень из предыдущего урока. В Python один вызов pow выполнит всю работу за Вас.
inv = pow(x, MOD - 2, MOD)Используйте его для деления
Чтобы разделить a на b по модулю, умножьте a на обратный элемент b. Остаток в точности равен частному по модулю p.
ans = a * pow(b, MOD - 2, MOD) % MODНикогда не находите обратный элемент для нуля
У 0 нет обратного элемента, поскольку никакое число, умноженное на ноль, не даст единицу. Не допускайте деления на значение, которое после взятия остатка по модулю становится нулём.
Стоимость вычисления одного обратного элемента
Каждое обращение по теореме Ферма — это одно быстрое возведение в степень, поэтому оно занимает время O(log p). Для нескольких делений это недорого, но при миллионах операций стоимость складывается.
Подсказка о пакетном вычислении обратных элементов
Если требуется много обратных элементов, заранее вычислите их одним хитрым линейным проходом вместо отдельного вызова pow для каждого элемента. Это понадобится Вам далее для nCr.
Быстрая проверка
Какая степень даёт обратный элемент по простому модулю?
Итоги
Теперь Вы умеете выполнять деление по простому модулю, умножая на обратный элемент по модулю, который вычисляется как x в степени p минус 2 с помощью pow. Только никогда не находите обратный элемент для нуля. ✅
Часто задаваемые вопросы
Урок «Обратный элемент по модулю через теорему Ферма» бесплатный?
Да — полный текст урока «Обратный элемент по модулю через теорему Ферма» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Обратный элемент по модулю через теорему Ферма»?
Безопасно делите по модулю Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Обратный элемент по модулю через теорему Ферма»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Работа по модулю простого числа
- Быстрое модульное возведение в степень
- Обратный элемент по модулю через теорему Ферма
- nCr с предварительно вычисленными факториалами