Рубрики

Вычислить nCr% p | Набор 3 (с использованием маленькой теоремы Ферма)

Математика

Учитывая три числа n, r и p, вычислим значение n C r mod p. Здесь p — простое число, большее n. Здесь n C r — биномиальный коэффициент .

Пример:

Input:  n = 10, r = 2, p = 13
Output: 6
Explanation: 10C2 is 45 and 45 % 13 is 6.

Input:  n = 6, r = 2, p = 13
Output: 2

Мы обсудили следующие методы в предыдущих постах.
Вычислить n C r % p | Комплект 1 (Введение и решение для динамического программирования)
Вычислить n C r % p | Набор 2 (теорема Лукаса)

В этом посте обсуждается решение на основе теоремы Ферма.

Фон:
Маленькая теорема Ферма и модульное обратное
Маленькая теорема Ферма утверждает, что если p простое число, то для любого целого числа a число a p — a кратно p. В обозначениях модульной арифметики это выражается как:
а р = а (мод р)
Например, если a = 2 и p = 7, 2 7 = 128 и 128 — 2 = 7 × 18 — это целое число, кратное 7.

Если a не делится на p, маленькая теорема Ферма эквивалентна утверждению a p — 1 — 1 — целое число, кратное p, т.е.
а р-1 = 1 (мод р)

Если мы умножим обе стороны на -1 , мы получим.
а р-2 = а -1 (мод р)

Таким образом, мы можем найти модульную инверсию как p-2 .

Исчисление:

We know the formula for  nCrnCr = fact(n) / (fact(r) x fact(n-r)) 
Here fact() means factorial.

 nCr % p = (fac[n]* modIverse(fac[r]) % p *
               modIverse(fac[n-r]) % p) % p;
Here modIverse() means modular inverse under
modulo p.

Ниже приведена реализация вышеуказанного алгоритма. В следующей реализации массив fac [] используется для хранения всех вычисленных факторных значений.

C ++

// Модульное обратное решение
// вычисляем nCr% p
#include<bits/stdc++.h>

using namespace std;

  
/ * Итеративная функция для вычисления (x ^ y)% p

  в O (log y) * /

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 ^ (- 1) mod p

int modInverse(int n, int p)

{

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

}

  
// Возвращает nCr% p, используя маленький Ферма
// теорема.

int nCrModPFermat(int n, int r, int p)

{

   // Базовый вариант

   if (r==0)

      return 1;

  

    // Заполняем факториальный массив так, чтобы мы

    // можно найти все факториалы r, n

    // и номер

    int fac[n+1];

    fac[0] = 1;

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

        fac[i] = fac[i-1]*i%p;

  

    return (fac[n]* modInverse(fac[r], p) % p *

            modInverse(fac[n-r], p) % p) % p;

}

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

int main()

{

    // p должно быть простым числом больше n.

    int n = 10, r = 2, p = 13;

    cout << "Value of nCr % p is "

         << nCrModPFermat(n, r, p);

    return 0;

}

Джава

// Модульное обратное решение
// вычисляем nCr%

import java .io.*;

  

class GFG {

      

    / * Итеративная функция для расчета

    (x ^ y)% p в O (log y) * /

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

    {

          

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

        int res = 1;

      

        // Обновление x, если оно больше или

        // равно p

        x = 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 ^ (- 1) mod p

    static int modInverse(int n, int p)

    {

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

    }

      

    // Возвращает nCr% p, используя Ферма

    // маленькая теорема.

    static int nCrModPFermat(int n, int r,

                                    int p)

    {

          

        // Базовый вариант

        if (r == 0)

            return 1;

      

        // Заполняем факториальный массив так, чтобы мы

        // можно найти все факториалы r, n

        // и номер

        int[] fac = new int[n+1];

        fac[0] = 1;

          

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

            fac[i] = fac[i-1] * i % p;

      

        return (fac[n]* modInverse(fac[r], p)

                % p * modInverse(fac[n-r], p)

                                    % p) % p;

    }

      

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

    public static void main(String[] args)

    {

          

        // p должно быть простым числом больше n.

        int n = 10, r = 2, p = 13;

        System.out.println("Value of nCr % p is "

                + nCrModPFermat(n, r, p));

    }

}

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

python3

# Python3 функция для
# рассчитать nCr% p

def ncr(n, r, p):

    # инициализировать числитель

    # и знаменатель

    num = den = 1 

    for i in range(r):

        num = (num * (n - i)) % p

        den = (den * (i + 1)) % p

    return (num * pow(den, 

            p - 2, p)) % p

  
# p должно быть простым
# больше чем n

n, r, p = 10, 2, 13

print("Value of nCr % p is", 

               ncr(n, r, p))

C #

// Модульное обратное решение
// вычисляем nCr% p

using System;

  

class GFG {

      

    / * Итеративная функция для расчета

    (x ^ y)% p в O (log y) * /

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

    {

          

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

        int res = 1;

      

        // Обновление x, если оно больше или

        // равно p

        x = 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 ^ (- 1) mod p

    static int modInverse(int n, int p)

    {

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

    }

      

    // Возвращает nCr% p, используя Ферма

    // маленькая теорема.

    static int nCrModPFermat(int n, int r,

                                    int p)

    {

          

        // Базовый вариант

        if (r == 0)

            return 1;

      

        // Заполняем факториальный массив так, чтобы мы

        // можно найти все факториалы r, n

        // и номер

        int[] fac = new int[n+1];

        fac[0] = 1;

          

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

            fac[i] = fac[i-1] * i % p;

      

        return (fac[n]* modInverse(fac[r], p)

                % p * modInverse(fac[n-r], p)

                                    % p) % p;

    }

      

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

    static void Main()

    {

          

        // p должно быть простым числом больше n.

        int n = 10, r = 2, p = 13;

        Console.Write("Value of nCr % p is "

                  + nCrModPFermat(n, r, p));

    }

}

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

PHP

<?php
// Модульное обратное
// решение на основе
// вычисляем nCr% p

  
// Итеративная функция для
// вычислить (x ^ y)% p
// в O (log y)

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

{

      

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

    $res = 1; 

  

    // Обновить х, если это

    // больше или

    // равно p

    $x = $x % $p; 

  

    while ($y > 0)

    {

          

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

        // умножаем х

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

        if ($y & 1)

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

  

        // у должен быть

        // даже сейчас

        // y = y / 2

        $y = $y >> 1; 

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

    }

    return $res;

}

  
// Возвращает n ^ (- 1) mod p

function modInverse($n, $p)

{

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

}

  
// Возвращает nCr% p используя
// Ферма маленький
// теорема.

function nCrModPFermat($n, $r, $p)

{

      

    // Базовый вариант

    if ($r==0)

        return 1;

  

    // Заполняем факториальный массив так, чтобы мы

    // можно найти все факториалы r, n

    // и номер

    // $ FAC [$ п + 1];

    $fac[0] = 1;

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

        $fac[$i] = $fac[$i - 1] *

                        $i % $p;

  

    return ($fac[$n] * modInverse($fac[$r], $p) % $p *

             modInverse($fac[$n - $r], $p) % $p) % $p;

}

  

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

    // р должно быть простым

    // больше чем n.

    $n = 10;

    $r = 2;

    $p = 13;

    echo "Value of nCr % p is ",

         nCrModPFermat($n, $r, $p);

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


Выход:

Value of nCr % p is 6

Улучшения:
В конкурентном программировании мы можем предварительно вычислить fac [] для данного верхнего предела, чтобы нам не приходилось вычислять его для каждого тестового случая. Мы также можем везде использовать unsigned long long int, чтобы избежать переполнения.

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

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

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

Вычислить nCr% p | Набор 3 (с использованием маленькой теоремы Ферма)

0.00 (0%) 0 votes