学步园

题目地址： http://acm.hdu.edu.cn/showproblem.php?pid=4390

给出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)

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

/*
freopen("input.txt",  "r", stdin);  //读数据
freopen("output.txt", "w", stdout); //注释掉此句则输出到控制台
*/
typedef __int64 LL;
const int II=1000000007;
LL c[555][555];
int a[1020],n;
vector<int> xh;

 void Init()
 {
     int i,j;
     for(i=0;i<=500;i++)
     {
         c[i][0]=c[i][i]=1;
         for(j=1;j<i;j++)
             c[i][j]=(c[i-1][j]+c[i-1][j-1])%II;
     }
 }

void divide(int k)
{
    int i;
    for(i=2;i*i<=k;i++)
        while(k%i==0)
        {
            xh.push_back(i);
            k/=i;
        }
    if(k>1)
        xh.push_back(k);
}

LL get(int n,int m)
{
    return c[n+m-1][n-1];
}

int main()
{
    int i,j,k,tt;
    LL cnt,ans,temp;
    Init();
    while(cin>>n)
    {
        xh.clear();
        for(i=0;i<n;i++)
        {
            scanf("%d",&k);
            divide(k);
        }
        sort(xh.begin(),xh.end());
        cnt=0;
        memset(a,0,sizeof(a));
        a[0]=1;
        for(i=1;i<xh.size();i++)
        {
            if(xh[i]!=xh[i-1])
                a[++cnt]=1;
            else
                a[cnt]++;
        }
        ans=1;
        for(i=0;i<=cnt;i++)
            ans=(ans*get(n,a[i]))%II;
        for(i=1;i<n;i++)
        {
            temp=c[n][i];
            for(j=0;j<=cnt;j++)
                temp=(temp*get(n-i,a[j]))%II;
            if(i&1)//奇数
                ans=((ans-temp)%II+II)%II;
            else
                ans=(ans+temp)%II;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}