Number of N length sequences whose product is M | C ++ implementation of the above approach ; Function to calculate the value of ncr effectively ; Initializing the result ; Multiply and divide simultaneously to avoid overflow ; Return the answer ; Function to return the number of sequences of length N such that their product is M ; Hashmap to store the prime factors of M ; Calculate the prime factors of M ; If i divides M it means it is a factor Divide M by i till it could be divided to store the exponent ; Increase the exponent count ; If the number is a prime number greater than sqrt ( M ) ; Initializing the ans ; Multiply the answer for every prime factor ; it . second represents the exponent of every prime factor ; Return the result ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ncr ( int n , int r ) { int res = 1 ; for ( int i = 1 ; i <= r ; i += 1 ) { res *= ( n - r + i ) ; res /= i ; } return res ; } int NoofSequences ( int N , int M ) { unordered_map < int , int > prime ; for ( int i = 2 ; i <= sqrt ( M ) ; i += 1 ) { while ( M % i == 0 ) { prime [ i ] += 1 ; M /= i ; } } if ( M > 1 ) { prime [ M ] += 1 ; } int ans = 1 ; for ( auto it : prime ) { ans *= ( ncr ( N + it . second - 1 , N - 1 ) ) ; } return ans ; } int main ( ) { int N = 2 , M = 6 ; cout << NoofSequences ( N , M ) ; return 0 ; }