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: 5 C 2 = 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:
Este valor es siempre un número entero (digamos M).
donde p i es un número primo.
Por lo tanto, el número de factores de M es
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
16
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