Dado un gran número n y un primo p, ¡cómo calcular n de manera eficiente! % ¿pags?
Ejemplos:
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
Una solución ingenua es primero calcular n!, luego calcular n! % pags. Esta solución funciona bien cuando el valor de n! es pequeño. El valor de n! Generalmente se necesita % p para valores grandes de n cuando n! no puede caber en una variable y provoca un desbordamiento. Entonces computando n! y luego usar un operador modular no es una buena idea ya que habrá un desbordamiento incluso para valores ligeramente mayores de n y r.
Los siguientes son diferentes métodos.
Método 1 (Simple)
Una solución simple es multiplicar uno por uno el resultado con i bajo el módulo p. Entonces, el valor del resultado no va más allá de p antes de la próxima iteración.
C++
// Simple method to compute n! % p
#include <bits/stdc++.h>
using namespace std;
// Returns value of n! % p
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;
}
// Driver program
int main()
{
int n = 25, p = 29;
cout << modFact(n, p);
return 0;
}
Java
// Simple method to compute n! % p
import java.io.*;
class GFG
{
// Returns value of n! % p
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;
}
// Driver Code
public static void main (String[] args)
{
int n = 25, p = 29;
System.out.print(modFact(n, p));
}
}
// This code is contributed
// by aj_36
Python3
# Simple method to compute n ! % p # Returns value of n ! % p def modFact(n, p): if n >= p: return 0 result = 1 for i in range(1, n + 1): result = (result * i) % p return result # Driver Code n = 25; p = 29 print (modFact(n, p)) # This code is contributed by Shreyanshi Arun.
C#
// Simple method to compute n! % p
using System;
class GFG {
// Returns value of n! % p
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;
}
// Driver program
static void Main()
{
int n = 25, p = 29;
Console.Write(modFact(n, p));
}
}
// This code is contributed by Anuj_67
PHP
<?php
// PHP Simple method to compute n! % p
// Returns value of n! % p
function modFact($n, $p)
{
if ($n >= $p)
return 0;
$result = 1;
for ($i = 1; $i <= $n; $i++)
$result = ($result * $i) % $p;
return $result;
}
// Driver Code
$n = 25; $p = 29;
echo modFact($n, $p);
// This code is contributed by Ajit.
?>
Javascript
<script>
// Simple method to compute n! % p
// Returns value of n! % p
function modFact(n,p)
{
if (n >= p)
return 0;
let result = 1;
for (let i = 1; i <= n; i++)
result = (result * i) % p;
return result;
}
// Driver Code
let n = 25, p = 29;
document.write(modFact(n, p));
// This code is contributed by Rajput-Ji
</script>
Producción :
5
Complejidad temporal: O(n).
Espacio auxiliar: O (1) ya que usa solo espacio constante
Método 2 (usando tamiz)
La idea se basa en la siguiente fórmula que se analiza aquí .
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.
La idea es encontrar todos los números primos menores que n usando la Criba de Eratóstenes . Para cada primo ‘p i ‘, encuentra la mayor potencia que divide a n!. Sea k i la mayor potencia . Calcule p i k i % p usando exponenciación modular . Multiplique esto con el resultado final bajo módulo p.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to Returns n % p
// using Sieve of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
// Returns largest power of p that divides n!
int largestPower(int n, int p)
{
// Initialize result
int x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n) {
n /= p;
x += n;
}
return x;
}
// Utility function to do modular exponentiation.
// It returns (x^y) % p
int power(int x, int y, int p)
{
int 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! % p
int modFact(int n, int p)
{
if (n >= p)
return 0;
int res = 1;
// Use Sieve of Eratosthenes to find all primes
// smaller than 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;
}
}
// Consider all primes found by Sieve
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
// Find the largest power of prime 'i' that divides n
int k = largestPower(n, i);
// Multiply result with (i^k) % p
res = (res * power(i, k, p)) % p;
}
}
return res;
}
// Driver method
int main()
{
int n = 25, p = 29;
cout << modFact(n, p);
return 0;
}
Java
import java.util.Arrays;
// Java program Returns n % p using Sieve of Eratosthenes
public class GFG {
// Returns largest power of p that divides n!
static int largestPower(int n, int p) {
// Initialize result
int x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n > 0) {
n /= p;
x += n;
}
return x;
}
// Utility function to do modular exponentiation.
// It returns (x^y) % p
static int power(int x, int y, int p) {
int 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 % 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! % p
static int modFact(int n, int p) {
if (n >= p) {
return 0;
}
int res = 1;
// Use Sieve of Eratosthenes to find all primes
// smaller than 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;
}
}
}
// Consider all primes found by Sieve
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
// Find the largest power of prime 'i' that divides n
int k = largestPower(n, i);
// Multiply result with (i^k) % p
res = (res * power(i, k, p)) % p;
}
}
return res;
}
// Driver method
static public void main(String[] args) {
int n = 25, p = 29;
System.out.println(modFact(n, p));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to Returns n % p # using Sieve of Eratosthenes # Returns largest power of p that divides n! def largestPower(n, p): # Initialize result x = 0 # Calculate x = n/p + n/(p^2) + n/(p^3) + .... while (n): n //= p x += n return x # Utility function to do modular exponentiation. # It returns (x^y) % p def power( x, y, p): 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! % p def modFact( n, p) : if (n >= p) : return 0 res = 1 # Use Sieve of Eratosthenes to find # all primes smaller than 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 # Consider all primes found by Sieve for i in range(2, n): if (isPrime[i]) : # Find the largest power of prime 'i' # that divides n k = largestPower(n, i) # Multiply result with (i^k) % p res = (res * power(i, k, p)) % p return res # Driver code if __name__ =="__main__": n = 25 p = 29 print(modFact(n, p)) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program Returns n % p using Sieve of Eratosthenes
using System;
public class GFG {
// Returns largest power of p that divides n!
static int largestPower(int n, int p) {
// Initialize result
int x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while (n > 0) {
n /= p;
x += n;
}
return x;
}
// Utility function to do modular exponentiation.
// It returns (x^y) % p
static int power(int x, int y, int p) {
int 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 % 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! % p
static int modFact(int n, int p) {
if (n >= p) {
return 0;
}
int res = 1;
// Use Sieve of Eratosthenes to find all primes
// smaller than 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;
}
}
}
// Consider all primes found by Sieve
for (int i = 2; i <= n; i++) {
if (isPrime[i]) {
// Find the largest power of prime 'i' that divides n
int k = largestPower(n, i);
// Multiply result with (i^k) % p
res = (res * power(i, k, p)) % p;
}
}
return res;
}
// Driver method
static public void Main() {
int n = 25, p = 29;
Console.WriteLine(modFact(n, p));
}
}
// This code is contributed by PrinciRaj19992
PHP
<?php
// PHP program to Returns n % p
// using Sieve of Eratosthenes
// Returns largest power of p that
// divides n!
function largestPower($n, $p)
{
// Initialize result
$x = 0;
// Calculate x = n/p + n/(p^2) + n/(p^3) + ....
while ($n)
{
$n = (int)($n / $p);
$x += $n;
}
return $x;
}
// Utility function to do modular exponentiation.
// It returns (x^y) % p
function power($x, $y, $p)
{
$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! % p
function modFact($n, $p)
{
if ($n >= $p)
return 0;
$res = 1;
// Use Sieve of Eratosthenes to find
// all primes smaller than 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;
}
}
// Consider all primes found by Sieve
for ($i = 2; $i <= $n; $i++)
{
if ($isPrime[$i])
{
// Find the largest power of
// prime 'i' that divides n
$k = largestPower($n, $i);
// Multiply result with (i^k) % p
$res = ($res * power($i, $k, $p)) % $p;
}
}
return $res;
}
// Driver Code
$n = 25;
$p = 29;
echo modFact($n, $p);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program Returns n % p
// using Sieve of Eratosthenes
// Returns largest power of p
// that divides n!
function largestPower(n, p)
{
// Initialize result
let x = 0;
// Calculate x = n/p + n/(p^2) +
// n/(p^3) + ....
while (n > 0) {
n = parseInt(n / p, 10);
x += n;
}
return x;
}
// Utility function to do
// modular exponentiation.
// It returns (x^y) % p
function power(x, y, p)
{
// Initialize result
let res = 1;
// Update x if it is more than or
x = x % p;
// equal to 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! % p
function modFact(n, p) {
if (n >= p) {
return 0;
}
let res = 1;
// Use Sieve of Eratosthenes
// to find all primes
// smaller than n
let isPrime = new Array(n + 1);
for(let i = 0;i<n+1;i++)
isPrime[i] = true;
for (let i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (let j = 2 * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
// Consider all primes found by Sieve
for (let i = 2; i <= n; i++) {
if (isPrime[i]) {
// Find the largest power of
// prime 'i' that divides n
let k = largestPower(n, i);
// Multiply result with (i^k) % p
res = (res * power(i, k, p)) % p;
}
}
return res;
}
let n = 25, p = 29;
document.write(modFact(n, p));
</script>
Producción:
5
Complejidad del tiempo: O(nlog(logn))
Espacio Auxiliar: O(n)
Este es un método interesante, pero la complejidad de tiempo de esto es más que el método simple, ya que la complejidad de tiempo de Sieve en sí es O (n log log n). Este método puede ser útil si tenemos disponible una lista de números primos menores o iguales a n.
Método 3 (usando el teorema de Wilson)
El teorema de Wilson establece que un número natural p > 1 es un número primo si y solo si
(p - 1) ! ≡ -1 mod p OR (p - 1) ! ≡ (p-1) mod p
Tenga en cuenta que n! % p es 0 si n >= p. Este método es principalmente útil cuando p está cerca del número de entrada n. Por ejemplo (25! % 29). Por el teorema de Wilson, sabemos que 28! es -1. Así que básicamente necesitamos encontrar [(-1) * inverse(28, 29) * inverse(27, 29) * inverse(26) ] % 29. La función inversa inverse(x, p) devuelve el inverso de x bajo módulo p (Ver esto para más detalles).
C++
// C++ program to compute n! % p using Wilson's Theorem
#include <bits/stdc++.h>
using namespace std;
// Utility function to do modular exponentiation.
// It returns (x^y) % p
int power(int x, unsigned int y, int p)
{
int 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;
}
// Function to find modular inverse of a under modulo p
// using Fermat's method. Assumption: p is prime
int modInverse(int a, int p)
{
return power(a, p - 2, p);
}
// Returns n! % p using Wilson's Theorem
int modFact(int n, int p)
{
// n! % p is 0 if n >= p
if (p <= n)
return 0;
// Initialize result as (p-1)! which is -1 or (p-1)
int res = (p - 1);
// Multiply modulo inverse of all numbers from (n+1)
// to p
for (int i = n + 1; i < p; i++)
res = (res * modInverse(i, p)) % p;
return res;
}
// Driver method
int main()
{
int n = 25, p = 29;
cout << modFact(n, p);
return 0;
}
Java
// Java program to compute n! % p
// using Wilson's Theorem
class GFG
{
// Utility function to do
// modular exponentiation.
// It returns (x^y) % p
static int power(int x, int y, int p)
{
int 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) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to find modular
// inverse of a under modulo p
// using Fermat's method.
// Assumption: p is prime
static int modInverse(int a, int p)
{
return power(a, p - 2, p);
}
// Returns n! % p using
// Wilson's Theorem
static int modFact(int n, int p)
{
// n! % p is 0 if n >= p
if (p <= n)
return 0;
// Initialize result as (p-1)!
// which is -1 or (p-1)
int res = (p - 1);
// Multiply modulo inverse of
// all numbers from (n+1) to p
for (int i = n + 1; i < p; i++)
res = (res * modInverse(i, p)) % p;
return res;
}
// Driver Code
public static void main(String[] args)
{
int n = 25, p = 29;
System.out.println(modFact(n, p));
}
}
// This code is contributed by mits
Python3
def gcdExtended(a,b): if(b==0): return a,1,0 g,x1,y1=gcdExtended(b,a%b) x1,y1 = y1,x1-(a//b)*y1 return g,x1,y1 # Driver code for _ in range(int(input())): n,m=map(int,input().split()) # if n>m, then there is a m in (1*2*3..n) % m such that # m % m=0 then whole ans is 0 if(n>=m): print(0) else: s=1 # Using Wilson's Theorem, (m-1)! % m = m - 1 # Since we need (1*2*3..n) % m # it can be divided into two parts # ( ((1*2*3...n) % m) * ((n+1)*(n+2)*...*(m-1)) )%m=m-1 # We only need to calculate 2nd part i.e. let s=((n+1)*(n+2)*...*(m-1)) ) % m for i in range(n+1,m): s=(s*i)%m # Then we divide (m-1) by s under modulo m means modulo inverse of s under m # It can be done by taking gcd extended g,a,b=gcdExtended(s,m) a=a%m # ans is (m-1)*(modulo inverse of s under m) print(((m-1)*a)%m) # This code is contributed by Himanshu Kaithal
C#
// C# program to compute n! % p
// using Wilson's Theorem
using System;
// Utility function to do modular
// exponentiation. It returns (x^y) % p
class GFG
{
public int power(int x, int y, int p)
{
int 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) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to find modular inverse
// of a under modulo p using Fermat's
// method. Assumption: p is prime
public int modInverse(int a, int p)
{
return power(a, p - 2, p);
}
// Returns n! % p using
// Wilson's Theorem
public int modFact(int n, int p)
{
// n! % p is 0 if n >= p
if (p <= n)
return 0;
// Initialize result as (p-1)!
// which is -1 or (p-1)
int res = (p - 1);
// Multiply modulo inverse of all
// numbers from (n+1) to p
for (int i = n + 1; i < p; i++)
res = (res * modInverse(i, p)) % p;
return res;
}
// Driver method
public static void Main()
{
GFG g = new GFG();
int n = 25, p = 29;
Console.WriteLine(g.modFact(n, p));
}
}
// This code is contributed by Soumik
PHP
<?php
// PHP program to compute
// n!% p using Wilson's Theorem
// Utility function to do
// modular exponentiation.
// It returns (x^y) % p
function power($x, $y, $p)
{
$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;
}
// Function to find modular
// inverse of a under modulo
// p using Fermat's method.
// Assumption: p is prime
function modInverse($a, $p)
{
return power($a, $p - 2, $p);
}
// Returns n! % p
// using Wilson's Theorem
function modFact( $n, $p)
{
// n! % p is 0
// if n >= p
if ($p <= $n)
return 0;
// Initialize result as
// (p-1)! which is -1 or (p-1)
$res = ($p - 1);
// Multiply modulo inverse
// of all numbers from (n+1)
// to p
for ($i = $n + 1; $i < $p; $i++)
$res = ($res *
modInverse($i, $p)) % $p;
return $res;
}
// Driver Code
$n = 25; $p = 29;
echo modFact($n, $p);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to compute n! % p
// using Wilson's Theorem
// Utility function to do modular
// exponentiation. It returns (x^y) % p
function power(x, y, p)
{
let 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) > 0)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Function to find modular inverse
// of a under modulo p using Fermat's
// method. Assumption: p is prime
function modInverse(a, p)
{
return power(a, p - 2, p);
}
// Returns n! % p using
// Wilson's Theorem
function modFact(n, p)
{
// n! % p is 0 if n >= p
if (p <= n)
return 0;
// Initialize result as (p-1)!
// which is -1 or (p-1)
let res = (p - 1);
// Multiply modulo inverse of all
// numbers from (n+1) to p
for (let i = n + 1; i < p; i++)
res = (res * modInverse(i, p)) % p;
return res;
}
let n = 25, p = 29;
document.write(modFact(n, p));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
5
La complejidad temporal de este método es O((pn)*Log)
Espacio auxiliar : O (1) porque solo se usan variables constantes
Método 4 (usando el algoritmo de prueba de primalidad)
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.
Tenga en cuenta que el paso 2 de la complejidad del tiempo del algoritmo anterior depende del algoritmo de prueba de primalidad que se utilice y del valor del primo más grande menor que n. El algoritmo AKS, por ejemplo, toma el tiempo O (Log 10.5 n).
Este artículo es una contribución de Ruchir Garg . 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