Что такое деление по модулю

Деление по модулю

Деление c остатком (деление по модулю, нахождение остатка от деления, остаток от деления) — арифметическая операция, результатом которой является два целых числа: частное и остаток от деления целого числа на другое целое число.

В программировании

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

Обозначение операции получения остатка в различных языках программирования см. в таблице справа.

См. также

• Делимость
• Деление (математика)
• Конгруэнтность (алгебра)
• Сравнение по модулю
• Кольцо (математика)
• Остаток от деления

Примечания

1. ↑ISO/IEC 14882:2003 : Programming languages — C++, 5.6.4: ISO, IEC, 2003 . «the binary % operator yields the remainder from the division of the first expression by the second. …. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined».

Ссылки

Wikimedia Foundation . 2010 .

• Деление клеток
• Деление с остастком

Полезное

Смотреть что такое «Деление по модулю» в других словарях:

• Деление по модулю — арифметическая операция, результатом которой является остаток от деления целого числа на другое целое число. См. также: Выражения Финансовый словарь Финам … Финансовый словарь
• деление (по модулю 2) — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN division (modulo 2) … Справочник технического переводчика
• Деление с остатком — Деление c остатком (деление по модулю, нахождение остатка от деления, остаток от деления) арифметическая операция, результатом которой является два целых числа: неполное частное и остаток от деления целого числа на другое целое число.… … Википедия
• Деление с остастком — Операция деления по модулю в различных языках программирования Язык Оператор Знак результата Делимое Ada mod Частное rem Делимое ASP Mod Не определено C (ISO 1990) % Не определено C (ISO 1999) … Википедия
• Деление (математика) — Запрос «Деление» перенаправляется сюда; для просмотра других значений см. Деление. Деление (операция деле … Википедия
• Сложение по модулю 2 — Рис. 1 График побитового исключающего «или» Сложение по модулю 2 (логическое сложение, исключающее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент) булева функция, а также … Википедия
• XOR — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Xor — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Исключающее ИЛИ — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Исключающее «или» — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия

• Обратная связь: Техподдержка, Реклама на сайте

• �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

• Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
• Искать во всех словарях
• Искать в переводах
• Искать в ИнтернетеИскать в этой же категории

Деление по модулю (вычисление остатка от деления)

Деление по модулю — это алгоритм нахождения остатка от деления первого натурального числа на второе.

% — деление по модулю. Эта операция взятия вычета по модулю (вычисление остатка от деления).

Результатом этой операции является остаток от целочисленного деления, например, если мы делим 11 на 3, то целых частей у нас получается 3, (так как 3*3=9), в остатке будет 2, это число и будет результатом деления по модулю, пример для языка C++:

11/3 = 3 целых 2 в остатке. Т.е. 11-3*3=2 11%3 = 2 (остаток) 27%23 = 1 целое 4 в остатке. Т.е. 27-1*23=4

Операцию деления по модулю, можно применять только к целочисленным данным. Попытки нарушить данное правило приведут к ошибке на этапе компиляции.

«Деление» по модулю

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

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

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

Например, $\frac = 4$, но

#Через бинарное возведение в степень

Малая теорема Ферма говорит, что для любого простого числа $p$ и любого целого числа $a$,

$$ a^p \equiv a \pmod p $$ Теперь два раза «поделим» этот известный результат на $a$: $$ a^p \equiv a \implies a^ \equiv 1 \implies a^ \equiv a^ $$

Получается, что $a^$ ведет себя как $a^$ относительно умножения по модулю, что нам и нужно.

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

  Этот подход простой и быстрый, однако следует помнить, что он работает только для простых модулей.

В случае составных модулей, по теореме Эйлера, число $a$ нужно возводить в степень $(\phi(m)-1)$, для чего нужно искать факторизацию.

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

Расширенный алгоритм Евклида можно использовать для решения в целых числах уравнений вида

$$ Ax + By = 1 $$ Подставим в качестве $A$ и $B$ соответственно $a$ и $m$: $$ ax + my = 1 $$ Одним из решений уравнения и будет $a^$, потому что если взять уравнение по модулю $m$, то получим $$ ax + my = 1 \iff ax \equiv 1 \iff x \equiv a^ \pmod m $$

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

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

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

#Упрощенная реализация

Сначала приведем реализацию, а потом поймем, почему она работает:

Докажем по индукции, что функция действительно возвращает обратный элемент.

Базовый случай очевиден: $1 \cdot 1 \equiv 1$.

Во втором случае проверим правильность формулы:

• $(1 — f(m \bmod a, a) \cdot m)$ делится на $a$, так как $f(m \bmod a, a) \equiv m^ \pmod a$.
• $\frac$ делится на $m$, так что итоговое выражение сравнимо с $\frac= a^$ по модулю $m$.

Почему ответ будет получаться в диапазоне от $0$ до $(m — 1)$, мы оставим читателю в качестве упражнения.

#Предподсчет обратных элементов

Чаще всего нам нужно искать обратный элемент в контексте комбинаторики.

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

Простой способ — это предпосчитать обычные факториалы и каждый раз вызывать inv один или два раза:

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

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

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

После этого обратный к $(a-1)!$ можно посчитать за $O(1)$ по формуле:

Все остальные обратные факториалы можно таким же образом итеративно подсчитать из предыдущего.

  Также существует метод нахождения обратных для всех чисел от $1$ до $(p - 1)$, но так как обычно модули большие, он не часто применим.

#Почему $10^9+7$?

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

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

Иногда можно встретить $998244353$. Оно обладает всеми свойствами кроме первого, но зато имеет применение в одном из вариантов быстрого преобразования Фурье. Его иногда добавляют даже в задачи, которые к нему не относятся, чтобы не раскрывать участникам тему.

Деление по модулю

Деление по модулю — арифметическая операция, результатом которой является остаток от деления целого числа на другое целое число.

См. также: Выражения

Финансовый словарь Финам .

• Делегирование кредита
• Дело Aicoa

Смотреть что такое «Деление по модулю» в других словарях:

• деление (по модулю 2) — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN division (modulo 2) … Справочник технического переводчика
• Деление по модулю — Операция деления по модулю в различных языках программирования Язык Оператор Знак результата Делимое Ada mod Частное rem Делимое ASP Mod Не определено C (ISO 1990) % Не определено C (ISO 1999) … Википедия
• Деление с остатком — Деление c остатком (деление по модулю, нахождение остатка от деления, остаток от деления) арифметическая операция, результатом которой является два целых числа: неполное частное и остаток от деления целого числа на другое целое число.… … Википедия
• Деление с остастком — Операция деления по модулю в различных языках программирования Язык Оператор Знак результата Делимое Ada mod Частное rem Делимое ASP Mod Не определено C (ISO 1990) % Не определено C (ISO 1999) … Википедия
• Деление (математика) — Запрос «Деление» перенаправляется сюда; для просмотра других значений см. Деление. Деление (операция деле … Википедия
• Сложение по модулю 2 — Рис. 1 График побитового исключающего «или» Сложение по модулю 2 (логическое сложение, исключающее «ИЛИ», строгая дизъюнкция, XOR, поразрядное дополнение, побитовый комплемент) булева функция, а также … Википедия
• XOR — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Xor — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Исключающее ИЛИ — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия
• Исключающее «или» — Сложение по модулю 2 (исключающее «ИЛИ», XOR, «сумма по модулю 2») ло­ги­чес­кая опе­ра­ция, по сво­ему при­ме­не­нию мак­си­маль­но при­бли­жен­ная к грам­ма­ти­чес­кой кон­струк­ции «либо … либо …». Это бинарная инфиксная опе­ра­ция, то есть… … Википедия

• Обратная связь: Техподдержка, Реклама на сайте

• �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,

WordPress, MODx.

• Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
• Искать во всех словарях
• Искать в переводах
• Искать в ИнтернетеИскать в этой же категории

Поделиться ссылкой на выделенное

Прямая ссылка:

… Нажмите правой клавишей мыши и выберите «Копировать ссылку»