Recuento de factores de combinación de N y K (nCk)

Dados los números enteros N y K , la tarea es encontrar el número de factores de ^N C _K . Dado que la respuesta puede ser muy grande, devuelva la cuenta de factores módulo 998244353.

Ejemplo:

Entrada: N = 5, K = 2
Salida: 4
Explicación: ⁵ C ₂ = 10 que tienen {1, 2, 5, 10} como sus divisores. Entonces la respuesta sería 4.

Entrada: N = 10, K = 3
Salida: 16

Enfoque: El problema se puede resolver con base en el siguiente hecho matemático:

$^{N}C_{K} = (N * (N-1)* \cdots * (N-K+1))/(K*(K-1)* \cdots *2*1)$

Este valor es siempre un número entero (digamos M).

$M = \prod_{i}^{}p_{i}^{e_{i}}$

donde p _i es un número primo.
Por lo tanto, el número de factores de M es

$M = \prod_{i}^{}{(e_{i}+1)}$

Basado en el hecho anterior, el problema se puede resolver encontrando los factores primos de M y sus exponentes. Para encontrar los factores primos de M, encuentra los factores primos del numerador y los factores primos del denominador

Siga los pasos que se mencionan a continuación para resolver el problema:

Realice la descomposición en factores primos de los primeros K números naturales usando la criba de Eratóstenes para encontrar los factores primos del denominador.
Del mismo modo, realice la descomposición en factores primos de los números naturales en el rango [N – K +1, N] para encontrar los factores primos del numerador.
Después de encontrar la descomposición en factores primos de todos los términos en el numerador y el denominador de ^N C _K , usa la fórmula que se muestra arriba para encontrar el número de factores de ^N C _K .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of factors
int divisorsOfNchooseK(long long N, long long K)
{
 
    // Parameter in time and space complexity
    long long M = max((long long)sqrt(N), K);
 
    // Sieve of eratosthenes for finding prime upto M
    vector<bool> prime(M + 1, true);
    prime[0] = prime[1] = false;
    for (long long p = 2; p * p < prime.size(); p++) {
        if (prime[p]) {
            for (long long i = 2 * p; i < prime.size();
                 i += p) {
                prime[i] = false;
            }
        }
    }
 
    // Store the denominator values in deno vector
    vector<long long> deno(K + 1);
 
    for (long long i = 1; i <= K; i++) {
        deno[i] = i;
    }
 
    // Store the numerator values in nume vector
    vector<long long> nume(K);
 
    long long offset = N - K + 1;
 
    for (long long i = 0; i < K; i++) {
        nume[i] = offset + i;
    }
 
    // Variable for storing answer
    long long ans = 1;
 
    // Iterate through all prime upto M
    for (long long p = 2; p < prime.size(); p++) {
        if (prime[p]) {
            // Store the power of p in
            // prime factorization of C(N, K)
            long long int power = 0;
 
            // Do prime factorization of deno terms
            for (long long i = p; i <= K; i += p) {
                while (deno[i] % p == 0) {
                    power--;
                    deno[i] /= p;
                }
            }
 
            // Do prime factorization of nume terms
            for (long long i
                 = ((N - K + 1) + p - 1) / p * p;
                 i <= N; i += p) {
                while (nume[i - offset] % p == 0) {
                    power++;
                    nume[i - offset] /= p;
                }
            }
            ans *= (power + 1);
            ans %= 998244353;
        }
    }
 
    // Find whether any term in
    // numerator is divisible by some prime
    // greater than √N
    for (long long i = N - K + 1; i <= N; i++) {
        if (nume[i - offset] != 1) {
            ans *= 2; // Coefficient of this prime will be 1
            ans %= 998244353;
        }
    }
 
    return ans;
}
// Driver code
int main()
{
    long long N = 10, K = 3;
 
    // Function call
    int ans = divisorsOfNchooseK(N, K);
    cout << ans;
    return 0;
}

Java

// Java program to implement the approach
import java.util.*;
 
class GFG {
 
  // Function to count the number of factors
  static long divisorsOfNchooseK(long N, long K)
  {
 
    // Parameter in time and space complexity
    long M = Math.max((long)Math.sqrt(N), K);
 
    // Sieve of eratosthenes for finding prime upto M
    boolean[] prime = new boolean[(int)M + 1];
    for (long x = 0; x < M + 1; x++) {
      prime[(int)x] = true;
    }
 
    prime[0] = prime[1] = false;
    for (long p = 2; p * p < prime.length; p++) {
      if (prime[(int)p] == true) {
        for (long i = 2 * p; i < prime.length;
             i += p) {
          prime[(int)i] = false;
        }
      }
    }
 
    // Store the denominator values in deno vector
    long[] deno = new long[(int)K + 1];
 
    for (long i = 1; i <= K; i++) {
      deno[(int)i] = i;
    }
 
    // Store the numerator values in nume vector
    long[] nume = new long[(int)K];
 
    long offset = N - K + 1;
 
    for (long i = 0; i < K; i++) {
      nume[(int)i] = offset + i;
    }
 
    // Variable for storing answer
    long ans = 1;
 
    // Iterate through all prime upto M
    for (long p = 2; p < prime.length; p++) {
      if (prime[(int)p] == true) {
        // Store the power of p in
        // prime factorization of C(N, K)
        long power = 0;
 
        // Do prime factorization of deno terms
        for (long i = p; i <= K; i += p) {
          while (deno[(int)i] % p == 0) {
            power--;
            deno[(int)i] /= p;
          }
        }
 
        // Do prime factorization of nume terms
        for (long i = ((N - K + 1) + p - 1) / p * p;
             i <= N; i += p) {
          while (nume[(int)(i - offset)] % p == 0) {
            power++;
            nume[(int)(i - offset)] /= p;
          }
        }
        ans *= (power + 1);
        ans %= 998244353;
      }
    }
 
    // Find whether any term in
    // numerator is divisible by some prime
    // greater than √N
    for (long i = N - K + 1; i <= N; i++) {
      if (nume[(int)(i - offset)] != 1) {
        ans *= 2; // Coefficient of this prime will
        // be 1
        ans %= 998244353;
      }
    }
 
    return ans;
  }
 
  // Driver code
  public static void main (String[] args) {
    long N = 10, K = 3;
 
    // Function call
    long ans = divisorsOfNchooseK(N, K);
    System.out.print(ans);
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# python3 program to implement the approach
 
import math
 
# Function to count the number of factors
def divisorsOfNchooseK(N, K) :
 
 
    # Parameter in time and space complexity
    M = max(int(math.sqrt(N)), K)
 
    # Sieve of eratosthenes for finding prime upto M
    prime = [ True for _ in range(M + 1) ]
    prime[0] = prime[1] = False
    for p in range(2, int(math.sqrt(len(prime)))) :
        if (prime[p]) :
            for i in range(2*p, len(prime), p) :
                prime[i] = False
         
 
    # Store the denominator values in deno vector
    deno = [ 0 for _ in range(K + 1) ]
 
    for i in range(1, K+1) :
        deno[i] = i
     
 
    # Store the numerator values in nume vector
    nume = [ 0 for _ in range(K) ]
 
    offset = N - K + 1
  
 
    for i in range(0, K) :
        nume[i] = offset + i
      
     
    # Variable for storing answer
    ans = 1
 
    # Iterate through all prime upto M
    for p in range(2, len(prime)) :
        if (prime[p]) :
            # Store the power of p in
            # prime factorization of C(N, K)
            power = 0
 
            # Do prime factorization of deno terms
            for i in range(p, K+1, p) :
                while (deno[i] % p == 0) :
                    power -= 1
                    deno[i] //= p
                 
             
            # Do prime factorization of nume terms
            for i in range(((N - K + 1) + p - 1) // p * p, N+1, p) :
                
                while (nume[i - offset] % p == 0) :
                    power += 1
                    nume[i - offset] //= p
                 
             
            ans *= (power + 1)
            ans %= 998244353
     
 
    # Find whether any term in
    # numerator is divisible by some prime
    # greater than √N
    for i in range(N - K + 1, N+1) :
        if (nume[i - offset] != 1) :
            ans *= 2 # Coefficient of this prime will be 1
            ans %= 998244353
 
    return ans
 
# Driver code
if __name__ == "__main__" :
 
    N, K = 10,  3
 
    # Function call
    ans = divisorsOfNchooseK(N, K)
    print(ans)
     
    # This code is contributed by rakeshsahni

C#

// C# program to implement the approach
using System;
class GFG {
 
    // Function to count the number of factors
    static long divisorsOfNchooseK(long N, long K)
    {
 
        // Parameter in time and space complexity
        long M = Math.Max((long)Math.Sqrt(N), K);
 
        // Sieve of eratosthenes for finding prime upto M
        bool[] prime = new bool[M + 1];
        for (long x = 0; x < M + 1; x++) {
            prime[x] = true;
        }
 
        prime[0] = prime[1] = false;
        for (long p = 2; p * p < prime.Length; p++) {
            if (prime[p] == true) {
                for (long i = 2 * p; i < prime.Length;
                     i += p) {
                    prime[i] = false;
                }
            }
        }
 
        // Store the denominator values in deno vector
        long[] deno = new long[K + 1];
 
        for (long i = 1; i <= K; i++) {
            deno[i] = i;
        }
 
        // Store the numerator values in nume vector
        long[] nume = new long[K];
 
        long offset = N - K + 1;
 
        for (long i = 0; i < K; i++) {
            nume[i] = offset + i;
        }
 
        // Variable for storing answer
        long ans = 1;
 
        // Iterate through all prime upto M
        for (long p = 2; p < prime.Length; p++) {
            if (prime[p] == true) {
                // Store the power of p in
                // prime factorization of C(N, K)
                long power = 0;
 
                // Do prime factorization of deno terms
                for (long i = p; i <= K; i += p) {
                    while (deno[i] % p == 0) {
                        power--;
                        deno[i] /= p;
                    }
                }
 
                // Do prime factorization of nume terms
                for (long i = ((N - K + 1) + p - 1) / p * p;
                     i <= N; i += p) {
                    while (nume[i - offset] % p == 0) {
                        power++;
                        nume[i - offset] /= p;
                    }
                }
                ans *= (power + 1);
                ans %= 998244353;
            }
        }
 
        // Find whether any term in
        // numerator is divisible by some prime
        // greater than √N
        for (long i = N - K + 1; i <= N; i++) {
            if (nume[i - offset] != 1) {
                ans *= 2; // Coefficient of this prime will
                          // be 1
                ans %= 998244353;
            }
        }
 
        return ans;
    }
   
    // Driver code
    public static void Main()
    {
        long N = 10, K = 3;
 
        // Function call
        long ans = divisorsOfNchooseK(N, K);
        Console.Write(ans);
    }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
 
// JavaScript program to implement the approach
 
// Function to count the number of factors
function divisorsOfNchooseK(N, K){
 
    // Parameter in time and space complexity
    let M = Math.max(Math.floor(Math.sqrt(N)), K);
 
    // Sieve of eratosthenes for finding prime upto M
    let prime = new Array(M + 1).fill(true);
    prime[0] = prime[1] = false;
    for (let p = 2; p * p < prime.length; p++) {
        if (prime[p]) {
            for (let i = 2 * p; i < prime.length;
                 i += p) {
                prime[i] = false;
            }
        }
    }
 
    // Store the denominator values in deno vector
    let deno = new Array(K+1).fill(0);
 
    for (let i = 1; i <= K; i++) {
        deno[i] = i;
    }
 
    // Store the numerator values in nume vector
    let nume = new Array(K).fill(0);
 
    let offset = N - K + 1;
    for (let i = 0; i < K; i++) {
        nume[i] = offset + i;
    }
 
    // Variable for storing answer
    let ans = 1;
 
    // Iterate through all prime upto M
    for (let p = 2; p < prime.length; p++) {
        if (prime[p]) {
            // Store the power of p in
            // prime factorization of C(N, K)
            let power = 0;
 
            // Do prime factorization of deno terms
            for (let i = p; i <= K; i += p) {
                while (deno[i] % p == 0) {
                    power--;
                    deno[i] = Math.floor(deno[i] / p);
                }
            }
             
            // Do prime factorization of nume terms
            for (let i = Math.floor(((N - K + 1) + p - 1) / p) * p; i <= N; i += p) {
                 
                while (nume[i - offset] % p == 0) {
                    power++;
                    nume[i - offset] = Math.floor(nume[i - offset]/p);
                }
            }
            ans *= (power + 1);
            ans %= 998244353;
        }
    }
 
    // Find whether any term in
    // numerator is divisible by some prime
    // greater than √N
    for (let i = N - K + 1; i <= N; i++) {
        if (nume[i - offset] != 1) {
            ans *= 2; // Coefficient of this prime will be 1
            ans %= 998244353;
        }
    }
 
    return ans;
}
 
// Driver code
let N = 10, K = 3;
 
// Function call
let ans = divisorsOfNchooseK(N, K);
document.write(ans);
 
// This code is contributed by  shinjanpatra
 
</script>

Producción

Complejidad de tiempo: O(M * loglogM)
Espacio auxiliar: O(M) donde M es max(√N, K)

Publicación traducida automáticamente

Artículo escrito por subhamgoyal2014 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta