You 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 modulo 1000000007 (109?+?7).
The first line contains positive integer n (1?≤?n?≤?500). The second line contains space-separated integers a1,?a2,?...,?an (1?≤?ai?≤?109).
In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo1000000007 (109?+?7).
1
15
1
3
1 1 2
3
2
5 7
4
In the second sample, the get a decomposition of number 2, you need any one number out of three to equal 2, and the rest to equal 1.
In the third sample, the possible ways of decomposing into ordered multipliers are [7,5], [5,7], [1,35], [35,1].
A decomposition of positive integer m into n ordered
multipliers is a cortege of positive integers b?=?{b1,?b2,?... bn} such
that 
.
Two decompositions b and c are
considered different, if there exists index i such
that bi?≠?ci.
给n个数 ， Ai , 对每个Ai 求质因子 ，然后将质因子保存在map.first ，将质因子的个数 保存在map.second
令质因子t有k个， 对每个质因子t， 我们将k个质因子 放在n 个位置上的任意位置，用n-1 个排成一行的相同的“1“ 的板 ，插入k（或在k中，或全在k左或右），将它分成n份。即有C(n+k-1,n-1)种 放置方案。然后，同理，放置剩下的质因子。
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<string.h> 5 #include<map> 6 #include<math.h> 7 8 using namespace std; 9 typedef long long LL; 10 const int Max_N = 17000; 11 const int Mod = 1000000007; 12 const int M = 1000; 13 int C[Max_N][M]; 14 map<int ,int >factor; // factor key = 质因子， value = 因子的个数 15 map<int ,int >::iterator it; 16 int n; 17 void init() // 由组合 c(n,r)= C(n-1,r)+C(n-1,r-1)特例 是 c(0,0)=0 当r=0||n=r c(n,r)=1 18 { 19 C[0][0]=1; 20 for(int i=1;i<Max_N;i++) 21 for(int j=0;j<=i && j<M ;j++) 22 { 23 if(j==0 || j==i) C[i][j]=1; 24 else C[i][j] = (C[i-1][j]+C[i-1][j-1])%Mod; 25 } 26 } 27 void Prime(int x) // 求 x 的因子 28 { 29 int i,num; 30 for(i=2;i*i<=x;i++) 31 { 32 if(x%i == 0) 33 { 34 num=0; 35 while(x%i == 0) 36 { 37 num++; 38 x/=i; 39 } 40 factor[i]+=num; // 记录所以 ai 中因子为 i 的个数 41 } 42 } 43 if(x!=1) 44 factor[x]++; 45 } 46 int main() 47 { 48 int k; 49 init(); 50 cin>> n; 51 52 LL ans=1; 53 factor.clear(); 54 for(int i=0;i<n;i++) 55 { 56 cin>>k; 57 Prime(k); 58 } 59 for(it=factor.begin();it!= factor.end();it++) 60 { 61 int t=(*it).second; 62 ans = (ans*C[t+n-1][n-1]) % Mod; 63 } 64 cout<<ans<<endl; 65 66 return 0 ; 67 }
codeforce Round #232 Div2 map + 质因子 +组合,布布扣,bubuko.com
codeforce Round #232 Div2 map + 质因子 +组合
原文：http://www.cnblogs.com/zn505119020/p/3575287.html