Dados tres números n, r y p, calcule el valor de n C r mod p. Aquí p es un número primo mayor que n. Aquí n C r es el Coeficiente Binomial .
Ejemplo:
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
Hemos discutido los siguientes métodos en publicaciones anteriores.
Calcule n C r % p | Conjunto 1 (Introducción y Solución de Programación Dinámica)
Calcule n C r % p | Conjunto 2 (Teorema de Lucas)
En esta publicación, se analiza la solución basada en el Teorema de Fermat.
Antecedentes:
el pequeño teorema de Fermat y el inverso modular
El pequeño teorema de Fermat establece que si p es un número primo, entonces para cualquier número entero a, el número a p – a es un número entero múltiplo de p. En la notación de la aritmética modular, esto se expresa como:
a p = a (mod p)
Por ejemplo, si a = 2 y p = 7, 2 7= 128, y 128 – 2 = 7 × 18 es un múltiplo entero de 7.
Si a no es divisible por p, el pequeño teorema de Fermat es equivalente al enunciado a p – 1 – 1 es un múltiplo entero de p, es decir,
a p -1 = 1 (mod p)
Si multiplicamos ambos lados por -1 , obtenemos.
a p-2 = a -1 (mod p)
Entonces podemos encontrar el inverso modular como p-2 .
Cálculo:
We know the formula for nCr
nCr = 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.
A continuación se muestra la implementación del algoritmo anterior. En la siguiente implementación, se utiliza una array fac[] para almacenar todos los valores factoriales calculados.
C++
// A modular inverse based solution to
// compute nCr % p
#include <bits/stdc++.h>
using namespace std;
/* Iterative Function to calculate (x^y)%p
in O(log y) */
unsigned long long power(unsigned long long x,
int y, int p)
{
unsigned long long res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Returns n^(-1) mod p
unsigned long long modInverse(unsigned long long n,
int p)
{
return power(n, p - 2, p);
}
// Returns nCr % p using Fermat's little
// theorem.
unsigned long long nCrModPFermat(unsigned long long n,
int r, int p)
{
// If n<r, then nCr should return 0
if (n < r)
return 0;
// Base case
if (r == 0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
unsigned long long 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;
}
// Driver program
int main()
{
// p must be a prime greater than n.
int n = 10, r = 2, p = 13;
cout << "Value of nCr % p is "
<< nCrModPFermat(n, r, p);
return 0;
}
Java
// A modular inverse based solution to
// compute nCr %
import java.io.*;
class GFG {
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Returns n^(-1) mod p
static int modInverse(int n, int p)
{
return power(n, p - 2, p);
}
// Returns nCr % p using Fermat's
// little theorem.
static int nCrModPFermat(int n, int r,
int p)
{
if (n<r)
return 0;
// Base case
if (r == 0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
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;
}
// Driver program
public static void main(String[] args)
{
// p must be a prime greater than n.
int n = 10, r = 2, p = 13;
System.out.println("Value of nCr % p is "
+ nCrModPFermat(n, r, p));
}
}
// This code is contributed by Anuj_67.
Python3
# Python3 function to
# calculate nCr % p
def ncr(n, r, p):
# initialize numerator
# and denominator
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 must be a prime
# greater than n
n, r, p = 10, 11, 13
print("Value of nCr % p is",
ncr(n, r, p))
C#
// A modular inverse based solution to
// compute nCr % p
using System;
class GFG {
/* Iterative Function to calculate
(x^y)%p in O(log y) */
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Returns n^(-1) mod p
static int modInverse(int n, int p)
{
return power(n, p - 2, p);
}
// Returns nCr % p using Fermat's
// little theorem.
static int nCrModPFermat(int n, int r,
int p)
{
if (n<r)
return 0;
// Base case
if (r == 0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
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;
}
// Driver program
static void Main()
{
// p must be a prime greater than n.
int n = 10, r = 11, p = 13;
Console.Write("Value of nCr % p is "
+ nCrModPFermat(n, r, p));
}
}
// This code is contributed by Anuj_67
PHP
<?php
// A modular inverse
// based solution to
// compute nCr % p
// Iterative Function to
// calculate (x^y)%p
// in O(log y)
function power($x, $y, $p)
{
// Initialize result
$res = 1;
// Update x if it
// is more than or
// equal to p
$x = $x % $p;
while ($y > 0)
{
// If y is odd,
// multiply x
// with result
if ($y & 1)
$res = ($res * $x) % $p;
// y must be
// even now
// y = y/2
$y = $y >> 1;
$x = ($x * $x) % $p;
}
return $res;
}
// Returns n^(-1) mod p
function modInverse($n, $p)
{
return power($n, $p - 2, $p);
}
// Returns nCr % p using
// Fermat's little
// theorem.
function nCrModPFermat($n, $r, $p)
{
if ($n<$r)
return 0;
// Base case
if ($r==0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
//$fac[$n+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;
}
// Driver Code
// p must be a prime
// greater than n.
$n = 10;
$r = 2;
$p = 13;
echo "Value of nCr % p is ",
nCrModPFermat($n, $r, $p);
// This code is contributed by Ajit.
?>
Javascript
<script>
// A modular inverse based solution
// to compute nCr % p
/* Iterative Function to calculate
(x^y)%p in O(log y) */
function power(x, y, p)
{
// Initialize result
let res = 1;
// Update x if it is more than or
// equal to p
x = x % p;
while (y > 0) {
// If y is odd, multiply x
// with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Returns n^(-1) mod p
function modInverse(n, p)
{
return power(n, p - 2, p);
}
// Returns nCr % p using Fermat's
// little theorem.
function nCrModPFermat(n, r, p)
{
if (n<r)
{
return 0;
}
// Base case
if (r == 0)
return 1;
// Fill factorial array so that we
// can find all factorial of r, n
// and n-r
let fac = new Array(n + 1);
fac[0] = 1;
for (let 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;
}
// p must be a prime greater than n.
let n = 10, r = 2, p = 13;
document.write("Value of nCr % p is " +
nCrModPFermat(n, r, p));
</script>
Value of nCr % p is 6
Mejoras:
en la programación competitiva, podemos precalcular fac[] para un límite superior dado de modo que no tengamos que calcularlo para cada caso de prueba. También podemos usar long long int sin firmar en todas partes para evitar desbordamientos.
Este artículo es una contribución de Nikhil Papisetty . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA