Array Product Problem:

Array Product

Array Product Problem Description You are given a list of N integers and another positive integer K. Write a program to compute the number of ways in which the product P of the given N integers can be expressed as a product of K positive integers (not necessarily distinct). The order of the factors in the expression is not important. For example, 1 x 2 x 3 and 2 x 3 x 1 are not counted as different ways of expressing 6 as a product of three integers. Constraints The product of the N integers <= 10^9 Each of the N integers <=5000 Input Format Output One line containing the number of ways in which the product of the N integers can be expressed as a product of K positive integers Explanation Example 1

 Input 

 2 4

 2 3 

Output 

 2

 Explanation The product of the given integers is 6. This can be expressed as a product of 4 integers in 2 ways: 1x1x1x6, 1x1x2x3

 Example 2

 Input 

 2 3

 4 16

 Output

 7 Explanation The product is 64. This can be expressed as a product of three integers in the following ways: 1 x 1 x 64 1 x 2 x 32 1 x 4 x 16 1 x 8 x 8 2 x 2 x 16 2 x 4 x 8 4 x 4 x 4

Solution

#include <stdio.h>
 int c=0;
 void product(int k,int i,int m)
 {
int j;
 if(k==0)
 {
if(i<=m)
{
 c++;
 return;
 }
 }
 else

 {
 if(i>m)
 return ;

 for(j=i;j<=m;j++)
 {
if(m%j == 0)
 product(k-1,j,m/j);
 }
 }
 }
 int main()
 {
 int n,k,a[10],m=1,i,j;
 scanf("%d%d",&n,&k);
 for(i=0;i<n;i++)
 {
 scanf("%d",&a[i]);
 m=m*a[i];
 }
 for(i=1;i<=m;i++)
 {
 if(m%i==0)
 product(k-2,i,m/i);
 }
 printf("%d\n",c);
 return 0;
 }