Number Sequence

Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Given a number sequence b

₁,b

₂…b

_n. Please count how many number sequences a

₁,a

₂,...,a

_n satisfy the condition that a

₁*a

₂*...*a

_n=b

₁*b

₂*…*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

₁, b

₂,...,b

_n(1<b

_i<=1000000, b

₁*b

₂*…*b

_n<=10

²⁵).

Output

For each test case, please print the answer module 1e9 + 7.

Sample Input

      2 3 4 

Sample Output

      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 

Source

将每一个数分解质因数，得到每个质因数出现的次数（和质数本身没有关系），然后就要用到容斥原理了，

也就是将每个质数出现的次数放到n个容器中去，这里要注意下1的情况也就是某个容器里面没有放数。

这样结果=总的方案数-有一个容器没放数+有2个容器没有放数……

将m个数放入n个容器的方法数有C(n+m-1,n-1) 。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))using namespace std ;typedef long long LL ;const int M_P=1008 ;const LL Mod=1000000007 ;bool isprime[M_P+8] ;int prime[M_P] ,id;map
                  
                   my_hash ;map
                   
                    ::iterator p ;void make_prime(){ id=0 ; memset(isprime,0,sizeof(isprime)) ; for(int i=2;i<=M_P;i++){ if(!isprime[i]) prime[++id]=i ; for(int j=1 ;j<=id&&i*prime[j]<=M_P;j++){ isprime[i*prime[j]]=1 ; if(i%prime[j]==0) break ; } }}LL C[258][258] ;void get_C(){ C[1][0]=C[1][1]=1 ; for(int i=2;i<=250;i++){ C[i][0]=C[i][i]=1 ; for(int j=1;j
                    
                     =Mod) C[i][j]%=Mod ; } }}void gao(int N){ for(int i=1;i<=id&&prime[i]*prime[i]<=N;i++){ if(N%prime[i]==0){ while(N%prime[i]==0){ my_hash[prime[i]]++ ; N/=prime[i] ; } } if(N==1) break ; } if(N!=1) my_hash[N]++ ;}vector
                     
                      vec ;int N ;LL Sum(){ LL ans=1 ; for(int k=0;k
                      
                       =Mod) ans%=Mod ; } for(int i=1;i<=N;i++){ LL sum=C[N][i] ; for(int k=0;k
                       
                        =Mod) sum%=Mod ; } if(i&1) ans-=sum ; else ans+=sum ; ans=(ans%Mod+Mod)%Mod ; } return ans ;}int main(){ make_prime() ; get_C() ; int M ; while(scanf("%d",&N)!=EOF){ my_hash.clear() ; vec.clear() ; for(int i=1;i<=N;i++){ scanf("%d",&M) ; gao(M) ; } for(p=my_hash.begin();p!=my_hash.end();p++) vec.push_back(p->second) ; cout<
                        
                         <