Dados tres números n , r y p , la tarea es calcular el valor de n C r % p.
Nota: p es un número sin cuadrados y el factor primo más grande de p ≤ 50.
Ejemplos:
Entrada : n = 10, r = 2, p = 13
Salida: 6
Explicación : 10 C 2 es 45 y 45 % 13= 6Entrada: n = 6, r = 2, p = 13
Salida : 2
Enfoque: Ya hemos discutido varios otros enfoques de este problema. La siguiente es la lista de los enfoques:
- https://www.geeksforgeeks.org/compute-ncr-p-set-1-introduction-and-dynamic-programming-solution/
- https://www.geeksforgeeks.org/compute-ncr-p-set-2-lucas-theorem/
- https://www.geeksforgeeks.org/compute-ncr-p-set-3-using-fermat-little-theorem/
Aquí discutiremos otro enfoque usando el concepto del Teorema de Lucas y el Teorema del Resto Chino . Entonces, si no conoce esos dos teoremas, revíselos siguiendo los enlaces que se proporcionan aquí.
Para resolver el problema, siga los pasos que se mencionan aquí.
- Primero, encuentra todos los factores primos de p .
- Cree un vector para almacenar el n C r % m para cada primo( m ) en factores primos de p usando el Teorema de Lucas.
- Ahora, utilizando el teorema chino del resto, calcule min_x tal que min_x % primes[i] = rem[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
class Solution {
public:
// Function to find the value of nCr % p
int nCrModM(int n, int r, int p)
{
// Finding prime factors of m
vector<int> primes = findPrimeFactors(p);
vector<int> rem;
// Storing nCr % m in rem
for (auto m : primes)
rem.push_back(Lucas(n, r, m));
// Chinese Remainder Theorem to
// find min_x
int min_x = 0;
while (true) {
bool found = true;
for (int i = 0; i < primes.size();
i++) {
if (min_x % primes[i] != rem[i]) {
found = false;
break;
}
}
if (found) {
return min_x;
}
min_x++;
}
// Return min_x;
return min_x;
}
// Function to utilize the Lucas theorem
int Lucas(int n, int r, int m)
{
// If (r > n) return 0;
if (r == 0)
return 1;
int ni = n % m;
int ri = r % m;
return (pascal(ni, ri, m)
* Lucas(n / m, r / m, m))
% m;
}
// Pascal triangle method to find nCr
ll pascal(int n, int r, int m)
{
if (r == 0 or r == n)
return 1;
// r = min(r, n - r);
int nCr[r + 1];
memset(nCr, 0, sizeof(nCr));
nCr[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = min(r, i); j > 0; j--)
nCr[j]
= (nCr[j] + nCr[j - 1]) % m;
}
return nCr[r];
}
// Function to find prime factors
// for a given number n
vector<int> findPrimeFactors(int n)
{
vector<int> primes;
if (n % 2 == 0) {
primes.push_back(2);
while (n % 2 == 0)
n >>= 1;
}
for (int i = 3; n > 1; i += 2) {
if (n % i == 0) {
primes.push_back(i);
while (n % i == 0)
n /= i;
}
}
// Return the vector
// storing the prime factors
return primes;
}
};
// Driver Code
int main()
{
int n = 10, r = 2, p = 13;
Solution obj;
// Function call
int ans = obj.nCrModM(n, r, p);
cout << ans;
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
class GFG{
// Function to find the value of nCr % p
public int nCrModM(int n, int r, int p)
{
// Finding prime factors of m
Vector<Integer> primes = findPrimeFactors(p);
Vector<Integer> rem = new Vector<Integer>();
// Storing nCr % m in rem
for (int m : primes)
rem.add(Lucas(n, r, m));
// Chinese Remainder Theorem to
// find min_x
int min_x = 0;
while (true) {
boolean found = true;
for (int i = 0; i < primes.size();
i++) {
if (min_x % primes.get(i) != rem.get(i)) {
found = false;
break;
}
}
if (found) {
return min_x;
}
min_x++;
}
// Return min_x;
//return min_x;
}
// Function to utilize the Lucas theorem
int Lucas(int n, int r, int m)
{
// If (r > n) return 0;
if (r == 0)
return 1;
int ni = n % m;
int ri = r % m;
return (pascal(ni, ri, m)
* Lucas(n / m, r / m, m))
% m;
}
// Pascal triangle method to find nCr
public int pascal(int n, int r, int m)
{
if (r == 0 || r == n)
return 1;
// r = Math.min(r, n - r);
int []nCr = new int[r + 1];
nCr[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = Math.min(r, i); j > 0; j--)
nCr[j]
= (nCr[j] + nCr[j - 1]) % m;
}
return nCr[r];
}
// Function to find prime factors
// for a given number n
Vector<Integer> findPrimeFactors(int n)
{
Vector<Integer> primes = new Vector<Integer>();
if (n % 2 == 0) {
primes.add(2);
while (n % 2 == 0)
n >>= 1;
}
for (int i = 3; n > 1; i += 2) {
if (n % i == 0) {
primes.add(i);
while (n % i == 0)
n /= i;
}
}
// Return the vector
// storing the prime factors
return primes;
}
// Driver Code
public static void main(String[] args)
{
int n = 10, r = 2, p = 13;
GFG obj = new GFG();
// Function call
int ans = obj.nCrModM(n, r, p);
System.out.print(ans);
}
}
// This code is contributed by shikhasingrajput
Python3
# python3 code for the above approach: class Solution: # Function to find the value of nCr % p def nCrModM(self, n, r, p): # Finding prime factors of m primes = self.findPrimeFactors(p) rem = [] # Storing nCr % m in rem for m in primes: rem.append(self.Lucas(n, r, m)) # Chinese Remainder Theorem to # find min_x min_x = 0 while (True): found = True for i in range(0, len(primes)): if (min_x % primes[i] != rem[i]): found = False break if (found): return min_x min_x += 1 # Return min_x; return min_x # Function to utilize the Lucas theorem def Lucas(self, n, r, m): # If (r > n) return 0; if (r == 0): return 1 ni = n % m ri = r % m return (self.pascal(ni, ri, m) * self.Lucas(n // m, r // m, m)) % m # Pascal triangle method to find nCr def pascal(self, n, r, m): if (r == 0 or r == n): return 1 # r = min(r, n - r); nCr = [0 for _ in range(r + 1)] nCr[0] = 1 for i in range(1, n+1): for j in range(min(r, i), 0, -1): nCr[j] = (nCr[j] + nCr[j - 1]) % m return nCr[r] # Function to find prime factors # for a given number n def findPrimeFactors(self, n): primes = [] if (n % 2 == 0): primes.append(2) while (n % 2 == 0): n >>= 1 i = 3 while(n > 1): if n % i == 0: primes.append(i) while(n % i == 0): n //= i i += 2 # Return the vector # storing the prime factors return primes # Driver Code if __name__ == "__main__": n = 10 r = 2 p = 13 obj = Solution() # Function call ans = obj.nCrModM(n, r, p) print(ans) # This code is contributed by rakeshsahni
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
class GFG {
// Function to find the value of nCr % p
public int nCrModM(int n, int r, int p)
{
// Finding prime factors of m
List<int> primes = findPrimeFactors(p);
List<int> rem = new List<int>();
// Storing nCr % m in rem
foreach(var m in primes) rem.Add(Lucas(n, r, m));
// Chinese Remainder Theorem to
// find min_x
int min_x = 0;
while (true) {
bool found = true;
for (int i = 0; i < primes.Count; i++) {
if (min_x % primes[i] != rem[i]) {
found = false;
break;
}
}
if (found) {
return min_x;
}
min_x++;
}
// Return min_x;
// return min_x;
}
// Function to utilize the Lucas theorem
int Lucas(int n, int r, int m)
{
// If (r > n) return 0;
if (r == 0)
return 1;
int ni = n % m;
int ri = r % m;
return (pascal(ni, ri, m) * Lucas(n / m, r / m, m))
% m;
}
// Pascal triangle method to find nCr
public int pascal(int n, int r, int m)
{
if (r == 0 || r == n)
return 1;
// r = Math.min(r, n - r);
int[] nCr = new int[r + 1];
nCr[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = Math.Min(r, i); j > 0; j--)
nCr[j] = (nCr[j] + nCr[j - 1]) % m;
}
return nCr[r];
}
// Function to find prime factors
// for a given number n
List<int> findPrimeFactors(int n)
{
List<int> primes = new List<int>();
if (n % 2 == 0) {
primes.Add(2);
while (n % 2 == 0)
n >>= 1;
}
for (int i = 3; n > 1; i += 2) {
if (n % i == 0) {
primes.Add(i);
while (n % i == 0)
n /= i;
}
}
// Return the vector
// storing the prime factors
return primes;
}
// Driver Code
public static void Main(string[] args)
{
int n = 10, r = 2, p = 13;
GFG obj = new GFG();
// Function call
int ans = obj.nCrModM(n, r, p);
Console.WriteLine(ans);
}
}
// This code is contributed by phasing17
Producción
6
Complejidad de Tiempo: O(p + log(p * n))
Espacio Auxiliar: O(p)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA