Работа по модулю простого числа
Складывайте и умножайте, не выходя за пределы модуля
«Работа по модулю простого числа» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Зачем нужен остаток по модулю
Ответы в задачах могут стать огромными и намного превысить пределы любого целочисленного типа. Поэтому в задачах просят найти результат по модулю большого простого числа, чтобы числа оставались небольшими. 🔢
Знакомьтесь: знаменитый модуль
Чаще всего Вам встретится простое число 1000000007, которое часто записывают как 1e9+7. Оно достаточно велико, чтобы избежать совпадений, и достаточно мало, чтобы помещаться в 64 бита.
MOD = 1000000007Что означает остаток по модулю
Оператор взятия остатка возвращает остаток после деления. Поэтому 17 % 5 равно 2: при делении 17 на 5 остаток равен 2.
print(17 % 5) # 2Сложение остаётся в пределах модуля
Вы можете сначала сложить числа и взять остаток в конце или брать остаток по ходу вычислений. В обоих случаях остаток будет одинаковым, поэтому чаще уменьшайте числа, чтобы они оставались небольшими.
total = (a + b) % MODУмножение тоже остаётся в пределах модуля
То же правило действует для умножения: возьмите произведение по модулю простого числа. Python умеет работать с большими целыми числами, но взятие остатка сохраняет каждое значение небольшим и ускоряет вычисления.
prod = (a * b) % MODУменьшайте результат после каждого шага
В длинном цикле применяйте % MOD на каждой итерации. Это не позволяет числам разрастаться и сохраняет каждую операцию быстрой и предсказуемой.
ans = (ans * i) % MODВычитание может дать отрицательный результат
Вычитание во многих языках может дать отрицательный остаток. Перед окончательным взятием остатка прибавьте MOD, чтобы результат оказался в безопасном диапазоне от 0.
diff = (a - b + MOD) % MODУдобный оператор взятия остатка в Python
Хорошая новость: оператор % в Python уже возвращает неотрицательный результат при положительном модуле. Поэтому -1 % 7 даёт 6, а не -1, и дополнительная коррекция не нужна.
print(-1 % 7) # 6Остаток по модулю распределяется по операциям
Основная идея такова: (a op b) % m равно (a%m op b%m) % m для сложения и умножения. Благодаря этому перед объединением можно уменьшить исходные значения.
Деление — исключение
Сложение, вычитание и умножение корректно работают по модулю. Но обычное деление — нет: позднее в этом курсе Вам понадобится обратный элемент по модулю.
Задайте MOD один раз в начале
Определите MOD как константу в начале решения. Одно именованное значение лучше, чем множество вхождений 1000000007 в коде, где легко спрятаться опечатке.
MOD = 10**9 + 7Быстрая проверка
Зачем прибавлять MOD перед взятием остатка от результата вычитания?
Итоги
Теперь Вы умеете хранить огромные количества в небольшом виде с помощью простого модуля, например 1e9+7. На каждом шаге берите остаток после сложения, вычитания и умножения, учитывайте отрицательные значения, а деление оставьте для вычисления обратных элементов. 🎯
Часто задаваемые вопросы
Урок «Работа по модулю простого числа» бесплатный?
Да — полный текст урока «Работа по модулю простого числа» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Работа по модулю простого числа»?
Складывайте и умножайте, не выходя за пределы модуля Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Работа по модулю простого числа»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Работа по модулю простого числа
- Быстрое модульное возведение в степень
- Обратный элемент по модулю через теорему Ферма
- nCr с предварительно вычисленными факториалами