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
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