学步园

题目链接：

http://codeforces.com/problemset/problem/337/E

题目大意：

给n个数（n<=8)，每个节点有个数，求节点数最少的包含这n个数的树，使得该树的叶子节点为质数，且每个非叶子节点为所有儿子的乘积。

解题思路：

首先统计该n个数中非质数的所有的质因子的个数的和。相当于叶子节点，不过当某个数为另外一个数的父亲时，统计多了，所以后面要减去。

然后从大往后枚举每个数A做为一个树根，依次找到含质因数个数最多的那个且能整除A的数B做为A的儿子，此时B就可以做为A的儿子，可以省去A的质因数个数个节点。再把第一个儿子排除在外再找第二个儿子，，，如此类推知道不能找到一个节点做为他的儿子，此时保证了以它做为父亲时能最大减少节点的数量，因为无论怎样他都有占有这么多的因子数量。

最后再统计所有的树根，如果树根超过1的话，再增加一个树根。

代码：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;


//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);

#define Maxn 10
ll a[Maxn];
int b[Maxn];
bool vis[Maxn];

int main()
{
   int n;

   while(~scanf("%d",&n))
   {
      for(int i=1;i<=n;i++)
         scanf("%I64d",&a[i]);
      sort(a+1,a+n+1);
      memset(b,0,sizeof(b));
      ll ans=0;
      for(int i=1;i<=n;i++)
      {
         ll temp=a[i];
         for(ll j=2;j*j<=temp;j++)
         {
            while(temp%j==0)
               b[i]++,temp/=j;
         }
         if(temp!=1)
            b[i]++;
         if(b[i]!=1)
            ans+=b[i];
      } //求出a的质因数个数
      memset(vis,false,sizeof(vis));
      //容斥原理+贪心思想，先把公共质因子最多的安顿好。
      int num=0,la,p;
      //printf(":%I64d \n",ans);

      for(int i=n;i>=1;i--)
      {
         if(!vis[i]) //c[i]=0表示没有作为前面的数的因子出现
            num++;
         while(true)
         {
            la=0;
            for(int j=i-1;j>=1;j--)
            {
               if(!vis[j]&&a[i]%a[j]==0&&b[j]>la)
               {
                  la=b[j];
                  p=j;
               }
            }
            if(la) //说明找到了一个，继续找
            {
               //printf("i:%d a[i]:%I64d b:%I64d la:%I64d\n",i,a[i],b[p]);
               //system("pause");
               vis[p]=true;
               a[i]/=a[p];
               ans=ans-la+1; //公共因子算了两次，减去，并把该数加进去
            }
            else //没找到
               break;

         }
      }
      ans+=num; //这么多的树根
      if(num>1) //需要另外再找一个树根
         ans++;
      printf("%I64d\n",ans);
   }
   return 0;
}