Number Sequence
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 63 Accepted Submission(s): 28
Total Submission(s): 63 Accepted Submission(s): 28
Problem Description
Given a number sequence b 1,b 2…b n.
Please count how many number sequences a 1,a 2,...,a n satisfy the condition that a 1*a 2*...*a n=b 1*b 2*…*b n (a i>1).
Please count how many number sequences a 1,a 2,...,a n satisfy the condition that a 1*a 2*...*a n=b 1*b 2*…*b n (a i>1).
Input
The input consists of multiple test cases.
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b 1, b 2,...,b n(1<b i<=1000000, b 1*b 2*…*b n<=10 25).
For each test case, the first line contains an integer n(1<=n<=20). The second line contains n integers which indicate b 1, b 2,...,b n(1<b i<=1000000, b 1*b 2*…*b n<=10 25).
Output
For each test case, please print the answer module 1e9 + 7.
SampleInput
23 4
SampleOutput
4
Hint
For the sample input, P=3*4=12. Here are the number sequences that satisfy the condition: 2 6 3 4 4 3 6 2 题目：给出n个数，b1,b2,b3……bn，构造n个数，a1,a2,……an(ai>1)，使得a1*a2*a3……an=b1*b2……bn;
首先是将所有 的b进行素因子分解，则a和b的因子是完全一致的。
剩下的便是将所有b的因子，分给a
我们考虑某个素因子pi,如果有ci个，便成了子问题将ci个相同的物品放入到n个不同的容器中，种数为多少
但是要求ai>1，也就是容器不能为空，这是个问题。
我们考虑的是什么的情况，然后减去假设有一个确定是空的情况，发现可以用容斥原理解决
我们假设f[i]表示有i个容器的结果，c(n,i)*f[i]
将m个物品放到到不同的n个容器中，结果为c(n+m-1,n-1)
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 const int mod=1000000007;10 11 long long c[510][510];12 int n;13 vector vt;14 15 void Divide(int num){16 for(int i=2;i*i<=num;i++)17 while(num%i==0){18 num/=i;19 vt.push_back(i);20 }21 if(num>1)22 vt.push_back(num);23 }24 25 void Init(){26 for(int i=0;i<=500;i++){27 c[i][0]=c[i][i]=1;28 for(int j=1;j