C. On Number of Decompositions into Multipliers
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputYou are given an integer m as a product of integers a1, a2, ... an 
. Your task is to find the number of distinct decompositions of number m into the product of n ordered positive integers.
Decomposition into n products, given in the input, must also be considered in the answer. As the answer can be very large, print it modulo1000000007 (109 + 7).
Input
The first line contains positive integer n (1 ≤ n ≤ 500). The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).
Output
In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo 1000000007(109 + 7).
input
1
15
output
1
分析：用map存储每个素数的个数接着就是组合公式c(n+k-1,k-1),因为是乘法所以相当于往盒子里面放小球盒子可以为空。因此多出n个盒子
1 #include<cstring>
2 #include<cstdio>
3 #include<algorithm>
4 #include<map>
5 typedef long long LL;
6 using namespace std;
7 const int MAX =600;
8 const int F = 1e6+10;
9 const int MOD = 1e9+7;
10 map<int , int > m;
11 int a[MAX];
12 LL c[30000][MAX];
13 void getp(int n)
14 {
15 long long i;
16 for(i=2;(long long)i*i<=n;i++)
17 {
18 while(n%i==0)
19 {
20 m[i]++;
21 n/=i;
22 }
23 }
24 if( n != 1 ) m[n]++;
25 }
26 void init()
27 {
28 c[0][0]=1;
29 for(int i=0;i<20020;i++)
30 {
31 c[i][i]=c[i][0]=1;
32 for(int j=1;j<=min(i,MAX);j++)
33 {
34 c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
35 }
36 }
37 }
38 int main()
39 {
40 int n;
41 LL ans;
42 while(scanf("%d",&n)==1)
43 {
44 m.clear(); ans=1;
45 for(int i=0;i<n;i++)
46 {
47 scanf("%d",&a[i]);
48 getp(a[i]);
49 }
50 init();
51 //printf("s");
52 for(map<int,int> ::iterator it=m.begin();it!=m.end();it++)
53 {
54 int k=it->second;
55 ans=ans*c[k-1+n][n-1]%MOD;
56 }
57 printf("%I64d ",ans);
58 }
59 return 0;
2 #include<cstdio>
3 #include<algorithm>
4 #include<map>
5 typedef long long LL;
6 using namespace std;
7 const int MAX =600;
8 const int F = 1e6+10;
9 const int MOD = 1e9+7;
10 map<int , int > m;
11 int a[MAX];
12 LL c[30000][MAX];
13 void getp(int n)
14 {
15 long long i;
16 for(i=2;(long long)i*i<=n;i++)
17 {
18 while(n%i==0)
19 {
20 m[i]++;
21 n/=i;
22 }
23 }
24 if( n != 1 ) m[n]++;
25 }
26 void init()
27 {
28 c[0][0]=1;
29 for(int i=0;i<20020;i++)
30 {
31 c[i][i]=c[i][0]=1;
32 for(int j=1;j<=min(i,MAX);j++)
33 {
34 c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
35 }
36 }
37 }
38 int main()
39 {
40 int n;
41 LL ans;
42 while(scanf("%d",&n)==1)
43 {
44 m.clear(); ans=1;
45 for(int i=0;i<n;i++)
46 {
47 scanf("%d",&a[i]);
48 getp(a[i]);
49 }
50 init();
51 //printf("s");
52 for(map<int,int> ::iterator it=m.begin();it!=m.end();it++)
53 {
54 int k=it->second;
55 ans=ans*c[k-1+n][n-1]%MOD;
56 }
57 printf("%I64d ",ans);
58 }
59 return 0;
60 }