Рубрики

Вычислить! по модулю р

Учитывая большое число n и простое число p, как эффективно вычислить n! % п?

Примеры :

Input:  n = 5, p = 13
Output: 3
5! = 120 and 120 % 13 = 3

Input:  n = 6, p = 11
Output: 5
6! = 720 and 720 % 11 = 5

Наивным решением является сначала вычислить n !, а затем вычислить n! % п. Это решение прекрасно работает, когда значение n! маленький. Значение n! % p обычно требуется для больших значений n, когда n! не может поместиться в переменную и вызывает переполнение. Так что вычисляя! и тогда использование модульного оператора не является хорошей идеей, поскольку будет переполнение даже для немного больших значений n и r.

Ниже приведены разные методы.

Способ 1 (простой)
Простое решение состоит в том, чтобы один за другим умножить результат на i по модулю p. Таким образом, значение результата не выходит за пределы p до следующей итерации.

C ++

// Простой метод для вычисления n! % п
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает значение n! % п

int modFact(int n, int p)

{

    if (n >= p)

        return 0;

  

    int result = 1;

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

        result = (result * i) % p;

  

    return result;

}

  
// Драйвер программы

int main()

{

    int n = 25, p = 29;

    cout << modFact(n, p);

    return 0;

}

Джава

// Простой метод для вычисления n! % п

import java.io.*;

  

class GFG 

{

    // Возвращает значение n! % п

    static int modFact(int n,

                       int p)

    {

        if (n >= p)

            return 0;

      

        int result = 1;

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

            result = (result * i) % p;

      

        return result;

    }

      

    // Код драйвера

    public static void main (String[] args) 

    {

        int n = 25, p = 29;

        System.out.print(modFact(n, p));

    }

}

  
// Этот код добавлен
// от aj_36

python3

# Простой метод для вычисления n! % п

  
# Возвращает значение n! % п

def modFact(n, p):

    if n >= p:

        return 0    

  

    result = 1

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

        result = (result * i) %

  

    return result

  
Код водителя

n = 25; p = 29

print (modFact(n, p))

  
# Этот код предоставлен Shreyanshi Arun.

C #

// Простой метод для вычисления n! % п

using System;

   

class GFG {

       

    // Возвращает значение n! % п

    static int modFact(int n, int p)

    {

        if (n >= p)

            return 0;

      

        int result = 1;

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

            result = (result * i) % p;

      

        return result;

    }

      

    // Драйвер программы

    static void Main()

    {

        int n = 25, p = 29;

        Console.Write(modFact(n, p));

    }

}

  
// Этот код предоставлен Anuj_67

PHP

<?php
// PHP Простой метод для вычисления n! % п

  
// Возвращает значение n! % п

function modFact($n, $p)

{

    if ($n >= $p)

    return 0; 

  

    $result = 1;

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

        $result = ($result * $i) % $p

  

    return $result;

}

  
// Код драйвера

$n = 25; $p = 29;

echo modFact($n, $p);

  
// Этот код предоставлен Ajit.
?>


Выход :

5

Сложность времени этого решения O (n).

Способ 2 (с использованием сита)
Идея основана на следующей формуле обсуждается здесь .

The largest possible power of a prime pi that divides n is,
    ⌊n/pi⌋ + ⌊n/(pi2)⌋ +  ⌊n/(pi3)⌋ + .....+ 0 

Every integer can be written as multiplication of powers of primes.  So,
  n! = p1k1 * p2k2 * p3k3 * ....
  Where p1, p2, p3, .. are primes and 
        k1, k2, k3, .. are integers greater than or equal to 1.

Идея состоит в том, чтобы найти все простые числа, меньшие чем n, используя Сито Эратосфена . Для каждого простого числа 'p i ' найдите наибольшую степень его, которая делит n !. Пусть наибольшая сила будет k i . Вычислите p i k i % p, используя модульное возведение в степень . Умножьте это на конечный результат по модулю p.

Ниже приведена реализация вышеуказанной идеи.

C ++

// Программа на C ++ возвращает n% p
// используя сито эратосфена
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает наибольшую степень p, которая делит n!

int largestPower(int n, int p)

{

    // Инициализировать результат

    int x = 0;

  

    // Вычислить x = n / p + n / (p ^ 2) + n / (p ^ 3) + ....

    while (n) {

        n /= p;

        x += n;

    }

    return x;

}

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

int power(int x, int y, int p)

{

    int res = 1; // Инициализировать результат

    x = x % p; // Обновление x, если оно больше или

    // равно p

    while (y > 0) {

        // Если y нечетно, умножаем x на результат

        if (y & 1)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Возвращает n! % п

int modFact(int n, int p)

{

    if (n >= p)

        return 0;

  

    int res = 1;

  

    // Используйте сито Эратосфена, чтобы найти все простые числа

    // меньше чем n

    bool isPrime[n + 1];

    memset(isPrime, 1, sizeof(isPrime));

    for (int i = 2; i * i <= n; i++) {

        if (isPrime[i]) {

            for (int j = 2 * i; j <= n; j += i)

                isPrime[j] = 0;

        }

    }

  

    // Рассмотрим все простые числа, найденные Sieve

    for (int i = 2; i <= n; i++) {

        if (isPrime[i]) {

            // Находим наибольшую степень простого числа i, которое делит n

            int k = largestPower(n, i);

  

            // Умножаем результат на (i ^ k)% p

            res = (res * power(i, k, p)) % p;

        }

    }

    return res;

}

  
// Метод драйвера

int main()

{

    int n = 25, p = 29;

    cout << modFact(n, p);

    return 0;

}

Джава

import java.util.Arrays;

  
// Java-программа возвращает n% p, используя сито Эратосфена

public class GFG {

  
// Возвращает наибольшую степень p, которая делит n!

    static int largestPower(int n, int p) {

        // Инициализировать результат

        int x = 0;

  

        // Вычислить x = n / p + n / (p ^ 2) + n / (p ^ 3) + ....

        while (n > 0) {

            n /= p;

            x += n;

        }

        return x;

    }

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

    static int power(int x, int y, int p) {

        int res = 1; // Инициализировать результат

        x = x % p; // Обновление x, если оно больше или

        // равно p

        while (y > 0) {

            // Если y нечетно, умножаем x на результат

            if (y % 2 == 1) {

                res = (res * x) % p;

            }

  

            // у должен быть даже сейчас

            y = y >> 1; // y = y / 2

            x = (x * x) % p;

        }

        return res;

    }

  
// Возвращает n! % п

    static int modFact(int n, int p) {

        if (n >= p) {

            return 0;

        }

  

        int res = 1;

  

        // Используйте сито Эратосфена, чтобы найти все простые числа

        // меньше чем n

        boolean isPrime[] = new boolean[n + 1];

        Arrays.fill(isPrime, true);

        for (int i = 2; i * i <= n; i++) {

            if (isPrime[i]) {

                for (int j = 2 * i; j <= n; j += i) {

                    isPrime[j] = false;

                }

            }

        }

  

        // Рассмотрим все простые числа, найденные Sieve

        for (int i = 2; i <= n; i++) {

            if (isPrime[i]) {

                // Находим наибольшую степень простого числа i, которое делит n

                int k = largestPower(n, i);

  

                // Умножаем результат на (i ^ k)% p

                res = (res * power(i, k, p)) % p;

            }

        }

        return res;

    }

  
// Метод драйвера

    static public void main(String[] args) {

        int n = 25, p = 29;

        System.out.println(modFact(n, p));

  

    }

}
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа возвращает n% p
# использование сита эратосфена

  
# Возвращает наибольшую степень p, которая делит n!

def largestPower(n, p):

      

    # Инициализировать результат

    x = 0

      

    # Вычислить x = n / p + n / (p ^ 2) + n / (p ^ 3) + ....

    while (n):

        n //= p

        x +=

    return

  
# Полезная функция для модульного возведения в степень.
# Возвращает (x ^ y)% p

def power( x, y, p):

    res = 1 # Инициализировать результат

    x = x % p # Обновите x, если оно больше

              # или равно p

    while (y > 0) : 

          

        # Если y нечетно, умножьте x на результат

        if (y & 1) :

            res = (res * x) %

  

        # у должно быть даже сейчас

        y = y >> 1 # y = y / 2

        x = (x * x) %

  

    return res 

  
# Возвращает n! % п

def modFact( n, p) :

  

    if (n >= p) :

        return 0

  

    res = 1

  

    # Используйте Сито Эратосфена, чтобы найти

    # все простые числа меньше n

    isPrime = [1] * (n + 1

    i = 2

    while(i * i <= n): 

        if (isPrime[i]): 

            for j in range(2 * i, n, i) :

                isPrime[j] = 0

        i += 1

          

    # Рассмотрим все простые числа, найденные Sieve

    for i in range(2, n): 

        if (isPrime[i]) :

              

            # Найти наибольшую силу простого 'я'

            #, который делит n

            k = largestPower(n, i) 

  

            # Умножить результат на (i ^ k)% p

            res = (res * power(i, k, p)) %

  

    return res 

  
# Код драйвера

if __name__ =="__main__":

    n = 25

    p = 29

    print(modFact(n, p))

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

C #

// C # программа Возвращает n% p, используя сито Эратосфена

using System;

  

  

public class GFG { 

  
// Возвращает наибольшую степень p, которая делит n!

    static int largestPower(int n, int p) { 

        // Инициализировать результат

        int x = 0; 

  

        // Вычислить x = n / p + n / (p ^ 2) + n / (p ^ 3) + ....

        while (n > 0) { 

            n /= p; 

            x += n; 

        

        return x; 

    

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

    static int power(int x, int y, int p) { 

        int res = 1; // Инициализировать результат

        x = x % p; // Обновление x, если оно больше или

        // равно p

        while (y > 0) { 

            // Если y нечетно, умножаем x на результат

            if (y % 2 == 1) { 

                res = (res * x) % p; 

            

  

            // у должен быть даже сейчас

            y = y >> 1; // y = y / 2

            x = (x * x) % p; 

        

        return res; 

    

  
// Возвращает n! % п

    static int modFact(int n, int p) { 

        if (n >= p) { 

            return 0; 

        

  

        int res = 1; 

  

        // Используйте сито Эратосфена, чтобы найти все простые числа

        // меньше чем n

        bool []isPrime = new bool[n + 1]; 

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

            isPrime[i] = true;

        for (int i = 2; i * i <= n; i++) { 

            if (isPrime[i]) { 

                for (int j = 2 * i; j <= n; j += i) { 

                    isPrime[j] = false

                

            

        

  

        // Рассмотрим все простые числа, найденные Sieve

        for (int i = 2; i <= n; i++) { 

            if (isPrime[i]) { 

                // Находим наибольшую степень простого числа i, которое делит n

                int k = largestPower(n, i); 

  

                // Умножаем результат на (i ^ k)% p

                res = (res * power(i, k, p)) % p; 

            

        

        return res; 

    

  
// Метод драйвера

    static public void Main() { 

        int n = 25, p = 29; 

        Console.WriteLine(modFact(n, p)); 

  

    


// Этот код предоставлен PrinciRaj19992

PHP

<?php
// PHP-программа возвращает n% p
// используя сито эратосфена

  
// Возвращает наибольшую степень p,
// делит n!

function largestPower($n, $p)

{

    // Инициализировать результат

    $x = 0;

  

    // Вычислить x = n / p + n / (p ^ 2) + n / (p ^ 3) + ....

    while ($n

    {

        $n = (int)($n / $p);

        $x += $n;

    }

    return $x;

}

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

function power($x, $y, $p)

{

    $res = 1; // Инициализировать результат

    $x = $x % $p; // Обновление x, если оно больше

                  // чем или равно p

    while ($y > 0) 

    {

        // Если y нечетно, умножаем x на результат

        if ($y & 1)

            $res = ($res * $x) % $p;

  

        // у должен быть даже сейчас

        $y = $y >> 1; // y = y / 2

        $x = ($x * $x) % $p;

    }

    return $res;

}

  
// Возвращает n! % п

function modFact($n, $p)

{

    if ($n >= $p)

        return 0;

  

    $res = 1;

  

    // Используйте сито Эратосфена, чтобы найти

    // все простые числа меньше n

    $isPrime = array_fill(0, $n + 1, true);

    for ($i = 2; $i * $i <= $n; $i++) 

    {

        if ($isPrime[$i]) 

        {

            for ($j = 2 * $i; $j <= $n; $j += $i)

                $isPrime[$j] = 0;

        }

    }

  

    // Рассмотрим все простые числа, найденные Sieve

    for ($i = 2; $i <= $n; $i++) 

    {

        if ($isPrime[$i]) 

        {

            // Найти наибольшую силу

            // простое 'i', которое делит n

            $k = largestPower($n, $i);

  

            // Умножаем результат на (i ^ k)% p

            $res = ($res * power($i, $k, $p)) % $p;

        }

    }

    return $res;

}

  
// Код драйвера

$n = 25;

$p = 29;

echo modFact($n, $p);

  
// Этот код предоставлен mits
?>


Выход:

5

Это интересный метод, но временная сложность этого больше, чем простой метод, так как временная сложность самого Sieve равна O (n log log n). Этот метод может быть полезен, если у нас есть список простых чисел, меньших или равных n, доступных нам.

Метод 3 (Используя теорему Вильсона)
Теорема Вильсона утверждает, что натуральное число p> 1 является простым числом тогда и только тогда, когда

    (p - 1) ! ≡ -1   mod p 
OR  (p - 1) ! ≡  (p-1) mod p 

Обратите внимание, что n! % p равно 0, если n> = p. Этот метод в основном полезен, когда p близко к входному номеру n. Например (25!% 29). Из теоремы Вильсона мы знаем, что 28! это -1. Таким образом, нам нужно найти [(-1) * обратный (28, 29) * обратный (27, 29) * обратный (26)]% 29. Обратная обратная функция (x, p) возвращает обратное значение x по модулю p (Смотрите это для деталей).

C ++

// C ++ программа для вычисления! % p с использованием теоремы Вильсона
#include <bits/stdc++.h>

using namespace std;

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

int power(int x, unsigned int y, int p)

{

    int res = 1; // Инициализировать результат

    x = x % p; // Обновление x, если оно больше или

    // равно p

    while (y > 0) {

        // Если y нечетно, умножаем x на результат

        if (y & 1)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Функция для нахождения модульной инверсии под модулем p
// используя метод Ферма. Предположение: р простое

int modInverse(int a, int p)

{

    return power(a, p - 2, p);

}

  
// Возвращает n! % p с использованием теоремы Вильсона

int modFact(int n, int p)

{

    // n! % p равно 0, если n> = p

    if (p <= n)

        return 0;

  

    // Инициализировать результат как (p-1)! который равен -1 или (р-1)

    int res = (p - 1);

  

    // Умножаем по модулю инверсию всех чисел из (n + 1)

    // верх

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

        res = (res * modInverse(i, p)) % p;

    return res;

}

  
// Метод драйвера

int main()

{

    int n = 25, p = 29;

    cout << modFact(n, p);

    return 0;

}

Джава

// Java-программа для вычисления n! % п
// используя теорему Вильсона

class GFG

{

      
// Полезная функция для выполнения
// модульное возведение в степень.
// Возвращает (x ^ y)% p

static int power(int x, int y, int p)

{

    int res = 1; // Инициализировать результат

    x = x % p;   // Обновление x, если оно больше

                 // чем или равно p

    while (y > 0

    {

        // Если у нечетное, умножаем

        // х с результатом

        if ((y & 1) > 0)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Функция для поиска модульной
// обратное значение по модулю p
// используя метод Ферма.
// Предположение: p простое число

static int modInverse(int a, int p)

{

    return power(a, p - 2, p);

}

  
// Возвращает n! % p используя
// Теорема Вильсона

static int modFact(int n, int p)

{

    // n! % p равно 0, если n> = p

    if (p <= n)

        return 0;

  

    // Инициализировать результат как (p-1)!

    // который равен -1 или (р-1)

    int res = (p - 1);

  

    // Умножаем по модулю на обратное

    // все числа от (n + 1) до p

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

        res = (res * modInverse(i, p)) % p;

    return res;

}

  
// Код драйвера

public static void main(String[] args)

{

    int n = 25, p = 29;

    System.out.println(modFact(n, p));

}
}

  
// Этот код предоставлен mits

python3

# Python3 программа для вычисления
# п! % p с использованием теоремы Вильсона

  
# Сервисная функция, чтобы сделать модульную
# возведение в степень. Возвращает (x ^ y)% p

def power(x, y,p):

  

    res = 1; # Инициализировать результат

    x = x % p; # Обновите x, если оно больше

               # чем или равно p

    while (y > 0):

          

        # Если у нечетно, умножить

        # х с результатом

        if (y & 1):

            res = (res * x) % p;

  

        # у должно быть даже сейчас

        y = y >> 1; # y = y / 2

        x = (x * x) % p;

      

    return res

  
# Функция поиска модульного обратного
# по модулю р с использованием Ферма
# метод. Предположение: р простое

def modInverse(a, p):

  

    return power(a, p - 2, p)

      
# Возвращает n! % p используя
Теорема Вильсона

def modFact(n , p):

  

    # п! % p равно 0, если n> = p

    if (p <= n):

        return 0

  

    # Инициализировать результат как (p-1)!

    # который равен -1 или (р-1)

    res = (p - 1)

  

    # Умножить по модулю на обратную

    # все числа от (n + 1) до p

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

        res = (res * modInverse(i, p)) % p

    return res

  
# Код драйвера

n = 25

p = 29

print(modFact(n, p))

  
# Этот код предоставлен ihritik

C #

// C # программа для вычисления n! % п
// используя теорему Вильсона

using System;

  
// Сервисная функция для модульной работы
// возведение в степень. Возвращает (x ^ y)% p

class GFG

{

public int power(int x, int y, int p)

{

    int res = 1; // Инициализировать результат

    x = x % p; // Обновление x, если оно больше

               // чем или равно p

    while (y > 0) 

    {

        // Если у нечетное, умножаем

        // х с результатом

        if((y & 1) > 0)

            res = (res * x) % p;

  

        // у должен быть даже сейчас

        y = y >> 1; // y = y / 2

        x = (x * x) % p;

    }

    return res;

}

  
// Функция поиска модульного обратного
// из под модуля по р с использованием Ферма
// метод. Предположение: р простое

public int modInverse(int a, int p)

{

    return power(a, p - 2, p);

}

  
// Возвращает n! % p используя
// Теорема Вильсона

public int modFact(int n, int p)

{

    // n! % p равно 0, если n> = p

    if (p <= n)

        return 0;

  

    // Инициализировать результат как (p-1)!

    // который равен -1 или (р-1)

    int res = (p - 1);

  

    // Умножаем по модулю все на обратное

    // числа от (n + 1) до p

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

        res = (res * modInverse(i, p)) % p;

    return res;

}

  
// Метод драйвера

public static void Main()

{

    GFG g = new GFG();

    int n = 25, p = 29;

    Console.WriteLine(g.modFact(n, p));

}
}

  
// Этот код предоставлен Soumik

PHP

<?php
// PHP программа для вычисления
// n!% p с использованием теоремы Вильсона

  
// Полезная функция для выполнения
// модульное возведение в степень.
// Возвращает (x ^ y)% p

function power($x, $y, $p)

{

    $res = 1; // Инициализировать результат

    $x = $x % $p; // Обновить х, если это

                  // больше или равно p

    while ($y > 0) 

    {

        // Если у нечетное, умножаем

        // х с результатом

        if ($y & 1)

            $res = ($res * $x) % $p;

  

        // у должен быть даже сейчас

        $y = $y >> 1; // y = y / 2

        $x = ($x * $x) % $p;

    }

    return $res;

}

  
// Функция для поиска модульной
// обратное значение по модулю
// p с использованием метода Ферма.
// Предположение: p простое число

function modInverse($a, $p)

{

    return power($a, $p - 2, $p);

}

  
// Возвращает n! % п
// используя теорему Вильсона

function modFact( $n, $p)

{

    // n! % p равно 0

    // если n> = p

    if ($p <= $n)

        return 0;

  

    // Инициализировать результат как

    // (р-1)! который равен -1 или (р-1)

    $res = ($p - 1);

  

    // Умножаем по модулю обратно

    // всех чисел из (n + 1)

    // верх

    for ($i = $n + 1; $i < $p; $i++)

        $res = ($res

                modInverse($i, $p)) % $p;

    return $res;

}

  
// Код драйвера

$n = 25; $p = 29;

echo modFact($n, $p);

  
// Этот код предоставлен ajit
?>


Выход:

5

Временная сложность этого метода составляет O ((pn) * Logn)

Метод 4 (с использованием алгоритма теста Primality)

1) Initialize: result = 1
2) While n is not prime
    result = (result * n) % p
3) result = (result * (n-1)) % p  // Using Wilson's Theorem 
4) Return result.

Обратите внимание, что шаг 2 временной сложности вышеупомянутого алгоритма зависит от используемого алгоритма проверки простоты и значения наибольшего простого числа, меньшего, чем n. Алгоритм AKS , например, занимает время O (Log 10,5 n).

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

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

Вычислить! по модулю р

0.00 (0%) 0 votes