Count arrays of length K whose product of elements is same as that of given array | C ++ implementation of the approach ; To store the smallest prime factor for every number ; Initialize map to store count of prime factors ; Function to calculate SPF ( Smallest Prime Factor ) for every number till MAXN ; Marking smallest prime factor for every number to be itself ; Separately marking spf for every even number as 2 ; Checking if i is prime ; Marking SPF for all numbers divisible by i ; Marking spf [ j ] if it is not previously marked ; Function to factorize using spf and store in cnt ; Function to return n ! % p ; Initialize result ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; Initialize result ; Update x if it is >= p ; If y is odd , multiply x with result ; y must be even now y = y / 2 ; Function that returns n ^ ( - 1 ) mod p ; Function that returns nCr % p using Fermat 's little theorem ; Base case ; Fill factorial array so that we can find all factorial of r , n and n - r ; Function to return the count the number of possible arrays mod P of length K such that the product of all elements of that array is equal to the product of all elements of the given array of length N ; Initialize result ; Call sieve to get spf ; Factorize arr [ i ] , count and store its factors in cnt ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define MAXN  (ll)(1e5 + 1) NEW_LINE #define mod  (ll)(1e9 + 7) NEW_LINE ll spf [ MAXN ] ; map < ll , ll > cnt ; void sieve ( ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAXN ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } void factorize ( ll f ) { while ( f > 1 ) { ll x = spf [ f ] ; while ( f % x == 0 ) { cnt [ x ] ++ ; f /= x ; } } } ll factorial ( ll n , ll p ) { ll res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) res = ( res * i ) % p ; return res ; } ll power ( ll x , ll y , ll p ) { ll res = 1 ; x = x % p ; while ( y > 0 ) { if ( y & 1 ) res = ( res * x ) % p ; y = y >> 1 ; x = ( x * x ) % p ; } return res ; } ll modInverse ( ll n , ll p ) { return power ( n , p - 2 , p ) ; } ll nCrModP ( ll n , ll r , ll p ) { if ( r == 0 ) return 1 ; ll fac [ n + 1 ] ; fac [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) fac [ i ] = fac [ i - 1 ] * i % p ; return ( fac [ n ] * modInverse ( fac [ r ] , p ) % p * modInverse ( fac [ n - r ] , p ) % p ) % p ; } ll countArrays ( ll arr [ ] , ll N , ll K , ll P ) { ll res = 1 ; sieve ( ) ; for ( int i = 0 ; i < N ; i ++ ) { factorize ( arr [ i ] ) ; } for ( auto i : cnt ) { int ci = i . second ; res = ( res * nCrModP ( ci + K - 1 , K - 1 , P ) ) % P ; } return res ; } int main ( ) { ll arr [ ] = { 1 , 3 , 5 , 2 } , K = 3 ; ll N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << countArrays ( arr , N , K , mod ) ; return 0 ; }