Given integers N and K, the task is to find the number of factors of NCK. Since the answer can be very large return the count of factors modulo 998244353.
Example:
Input: N = 5, K = 2
Output: 4
Explanation: 5C2 = 10 which have {1, 2, 5, 10} as its divisors. So answer would be 4.Input: N = 10, K = 3
Output: 16
Approach: The problem can be solved based on the following mathematical fact:
This value is always a whole number (Let’s say M).
where pi is a prime number.
Therefore, number of factors of M is
Based on the above fact, the problem can be solved by finding the prime factors of M and their exponents. To find the prime factors of M, find the prime factors of the numerator and prime factors of the denominator
Follow the steps mentioned below to solve the problem:
- Do prime factorization of first K natural numbers using Sieve of Eratosthenes to find prime factors of denominator.
- Similarly, do prime factorization of natural numbers in the range [N – K +1, N] to find prime factors of numerator.
- After finding the prime factorization of all the terms in the numerator and denominator of NCK, use the formula shown above to find the number of factors of NCK.
Below is the implementation of the above approach:
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of factorsint 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 codeint main(){ long long N = 10, K = 3; // Function call int ans = divisorsOfNchooseK(N, K); cout << ans; return 0;} |
Java
// Java program to implement the approachimport 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 approachimport math# Function to count the number of factorsdef 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 codeif __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 approachusing 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 factorsfunction 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 codelet N = 10, K = 3;// Function calllet ans = divisorsOfNchooseK(N, K);document.write(ans);// This code is contributed by shinjanpatra</script> |
Output
16
Time Complexity: O(M * loglogM)
Auxiliary Space: O(M) where M is max(√N, K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
