Number of N length sequences whose product is M | 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
def ncr ( n , r ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 1 , r + 1 ) : NEW_LINE INDENT res *= ( n - r + i ) NEW_LINE res //= i NEW_LINE DEDENT return res NEW_LINE DEDENT def NoofSequences ( N , M ) : NEW_LINE INDENT prime = { } NEW_LINE for i in range ( 2 , int ( M ** ( .5 ) ) + 1 ) : NEW_LINE INDENT while ( M % i == 0 ) : NEW_LINE INDENT prime [ i ] = prime . get ( i , 0 ) + 1 NEW_LINE M //= i NEW_LINE DEDENT DEDENT if ( M > 1 ) : NEW_LINE INDENT prime [ M ] = prime . get ( M , 0 ) + 1 NEW_LINE DEDENT ans = 1 NEW_LINE for it in prime : NEW_LINE INDENT ans *= ( ncr ( N + prime [ it ] - 1 , N - 1 ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT N = 2 NEW_LINE M = 6 NEW_LINE print ( NoofSequences ( N , M ) ) NEW_LINE