Рубрики

По модулю 10 ^ 9 + 7 (1000000007)

В большинстве соревнований по программированию проблемы должны отвечать на результат в 10 ^ 9 + 7 по модулю. Причиной этого является проблема больших целых чисел, так что только эффективные алгоритмы могут решить их за разрешенное ограниченное время.

Что такое операция по модулю:
Остаток, полученный после операции деления на два операнда, называется операцией по модулю. Оператор для выполнения операции модуля — «%» . Например: a% b = c, что означает, что когда a делится на b, это дает остаток c, 7% 2 = 1, 17% 3 = 2.

Зачем нам нужно по модулю

  • Причиной использования Mod является предотвращение целочисленных переполнений. Самый большой целочисленный тип данных в C / C ++ — это unsigned long long int, который имеет 64 бита и может обрабатывать целые числа от 0 до (2 ^ 64 — 1). Но в некоторых проблемах, где скорость роста выпуска очень высока, этот большой диапазон длинных длин без знака может быть недостаточным.
    Предположим, что в 64-битной переменной «A» хранится 2 ^ 62, а в другой 64-битной переменной «B» — 2 ^ 63. Когда мы умножаем A и B, система не выдает ошибку или исключение во время выполнения. Он просто делает некоторые фиктивные вычисления и сохраняет фиктивный результат, потому что размер битов результата приходит после переполнения умножения.
  • В некоторых задачах для вычисления результата необходим обратный модуль, и это число очень помогает, потому что оно простое. Также это число должно быть достаточно большим, иначе модульные обратные методы могут не работать в некоторых ситуациях.

По этим причинам разработчики задач требуют дать ответ по модулю некоторого числа N.
Существуют определенные критерии, от которых зависит значение N:

  1. Он должен быть достаточно большим, чтобы соответствовать типу данных с наибольшим целочисленным значением, т.е. он гарантирует, что в результате переполнения не будет.
  2. Это должно быть простое число, потому что если мы возьмем mod из числа с помощью Prime, то результат, как правило, будет разнесен, то есть результаты будут очень разными по сравнению с mod числом с не простым числом, поэтому простые числа обычно используются для mod.

10 ^ 9 + 7 удовлетворяет обоим критериям. Это первое 10-значное простое число, которое также подходит для типа данных int. На самом деле, любое простое число меньше 2 ^ 30 будет хорошо, чтобы предотвратить возможные переполнения.

Как используется модуль?
Несколько распределительных свойств по модулю следующие:

  1. (a + b)% c = ((a% c) + (b% c))% c
  2. (a * b)% c = ((a% c) * (b% c))% c
  3. (a — b)% c = ((a% c) — (b% c))% c
  4. (a / b)% c = ((a% c) / (b% c))% c

Таким образом, модуль является дистрибутивным по +, * и — но не по / / [подробности см. В Модульном отделе ]

ПРИМЕЧАНИЕ . Результат (a% b) всегда будет меньше, чем b.

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

Example:
a = 145785635595363569532135132
b = 3151635135413512165131321321
c = 999874455222222200651351351
m = 1000000007
Print (a*b*c)%m.

Method 1:
First, multiply all the number and then take modulo:
(a*b*c)%m = (459405448184212290893339835148809
515332440033400818566717735644307024625348601572) % 
1000000007
a*b*c does not fit even in the unsigned long long 
int due to which system drop some of its most 
significant digits. Therefore, it gives the wrong answer.
(a*b*c)%m = 798848767

Method 2:
Take modulo at each intermediate steps:
i = 1
i = (i*a) % m    // i = 508086243
i = (i*b) % m    // i = 144702857
i = (i*c) % m    // i = 798848767
i = 798848767 

Method 2 always gives the correct answer.

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

C ++

unsigned long long factorial(int n)

{

    const unsigned int M = 1000000007;

    unsigned long long f = 1;

  

    for (int i = 1; i <= n; i++)

        f = f * i;  // НЕПРАВИЛЬНЫЙ ПОДХОД как

                    // f может превышать (2 ^ 64 - 1)

  

    return f % M;

}

python3

def factorial( n) :

    M = 1000000007

    f = 1

  

    for i in range(1, n + 1): 

        f = f * i # НЕПРАВИЛЬНЫЙ ПОДХОД как

                  # f может превышать (2 ^ 64 - 1)

  

    return f %

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C ++

unsigned long long factorial(int n)

{

    const unsigned int M = 1000000007;

  

    unsigned long long f = 1;

    for (int i = 1; i <= n; i++)

        f = (f*i) % M;  // Теперь е никогда не могу

                        // превышаем 10 ^ 9 + 7

    return f;

}

python3

def factorial( n) :

    M = 1000000007

    f = 1

  

    for i in range(1, n + 1): 

        f = (f * i) % M # Теперь е никогда не могу

                        # превышает 10 ^ 9 + 7

  

    return

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

Та же процедура может быть выполнена для добавления.
(a + b + c)% M совпадает с (((a + b)% M) + c)% M.
Выполняйте% M каждый раз, когда число добавляется, чтобы избежать переполнения.

Примечание. В большинстве языков программирования (например, в C / C ++) при выполнении модульной операции с отрицательными числами это дает отрицательный результат, например -5% 3 = -2, но результат, полученный после модульной операции, должен находиться в диапазоне 0. для n-1 означает -5% 3 = 1. Таким образом, для этого преобразуйте его в положительный модульный эквивалент.

C ++

int mod(int a, int m)

{

    return (a%m + m) % m;

}

python3

def mod(a, m):

    return (a%m + m) % m

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

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

Модульное мультипликативное обратное (MMI):
Мультипликативная инверсия числа y равна z тогда и только тогда, когда (z * y) == 1.
Деление числа x на другое число y аналогично умножению x на обратную величину мультипликативного значения y.
x / y == x * y ^ (- 1) == x * z (где z — мультипликативная обратная y).
В обычной арифметике, мультипликативная обратная y является значением с плавающей запятой. Пример: Мультипликативная обратная величина 7 равна 0,142…, 3 равна 0,333….
В математике модульная мультипликативная инверсия целого числа «а» представляет собой целое число «x», такое что произведение ax совпадает с 1 относительно модуля m.
ax = 1 (mod m)
Остаток после деления топора на целое число m равен 1.

Example:
If M = 7, the MMI of 4 is 2 as ( 4 * 2 ) %7 ==1,
If M = 11, the MMI of 7 is 8 as ( 7 * 8 )%11 ==1,
If M = 13, the MMI of 7 is 2 as ( 7 * 2 ) % 13==1.

Обратите внимание, что MMI числа могут быть разными для разных М.
Итак, если мы выполняем арифметику по модулю в нашей программе и нам нужен результат операции x / y, мы НЕ должны выполнять

z = (x/y) % M;

вместо этого мы должны выполнить

y_inv = findMMI(y, M);
z = (x * y_inv) % M;

Теперь остается один вопрос .. Как найти MMI числа n.
Существует два алгоритма для поиска MMI числа. Первый — это алгоритм расширенного евклидова, а второй — маленькая теорема Ферма .
Вы можете найти оба метода в данной ссылке:
Модульный мультипликативный обратный

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

Ссылки:
https://www.quora.com/What-exactly-is-print-it-modulo-10-9-+-7-in-competitive-programming-websites
https://discuss.codechef.com/questions/4698/use-of-modulo-1000007-in-competitions
https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/

Эта статья предоставлена Акашем Гуптой . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

По модулю 10 ^ 9 + 7 (1000000007)

0.00 (0%) 0 votes