Divisor Tree

题意翻译

题目描述 小明创建了一个有根树满足下面三个条件 树上的每个结点包含一个正整数 对于叶子结点上的每个数都是素数 对于任一个非叶子结点，该结点上的数等于所有他子结点上的数的乘积 现在小明有一个长度为n的数组a1,a2,…,an。数组中任意两个数互不相同，他想将这些数放在如上面描述的树上。对于数组中的每个ai,保证树上至少有一个结点是包含ai的。总所周知，构造出这样一棵树是很简单的，但是小明自己建出来的树包含的结点个数太多了，现在请你帮忙构造出这样一棵树，使得这棵树的结点数量越少越好。 输入格式 第一行一个整数n(n<=8)代表数组长度 接下来一行n个正整数用空格分开代表ai(ai<=10^12) 输出格式 一行一个整数代表最少的结点个数 输入样例1 2 6 10 输出样例1 7 输入样例2 4 6 72 8 4 输出样例2 12 输入样例3 1 7 输出样例3 1

题目描述

A divisor tree is a rooted tree that meets the following conditions: - Each vertex of the tree contains a positive integer number. - The numbers written in the leaves of the tree are prime numbers. - For any inner vertex, the number within it is equal to the product of the numbers written in its children. Manao has $ n $ distinct integers $ a_{1},a_{2},...,a_{n} $ . He tries to build a divisor tree which contains each of these numbers. That is, for each $ a_{i} $ , there should be at least one vertex in the tree which contains $ a_{i} $ . Manao loves compact style, but his trees are too large. Help Manao determine the minimum possible number of vertices in the divisor tree sought.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=8 $ ). The second line contains $ n $ distinct space-separated integers $ a_{i} $ ( $ 2<=a_{i}<=10^{12} $ ).

输出格式

Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers $ a_{i} $ .

输入输出样例

输入样例 #1

2
6 10

输出样例 #1

7

输入样例 #2

4
6 72 8 4

输出样例 #2

12

输入样例 #3

1
7

输出样例 #3

1

说明

Sample 1. The smallest divisor tree looks this way:  Sample 2. In this case you can build the following divisor tree:  Sample 3. Note that the tree can consist of a single vertex.

题意翻译

题目描述 小明创建了一个有根树满足下面三个条件 树上的每个结点包含一个正整数 对于叶子结点上的每个数都是素数 对于任一个非叶子结点，该结点上的数等于所有他子结点上的数的乘积 现在小明有一个长度为n的数组a1,a2,…,an。数组中任意两个数互不相同，他想将这些数放在如上面描述的树上。对于数组中的每个ai,保证树上至少有一个结点是包含ai的。总所周知，构造出这样一棵树是很简单的，但是小明自己建出来的树包含的结点个数太多了，现在请你帮忙构造出这样一棵树，使得这棵树的结点数量越少越好。 输入格式 第一行一个整数n(n<=8)代表数组长度 接下来一行n个正整数用空格分开代表ai(ai<=10^12) 输出格式 一行一个整数代表最少的结点个数 输入样例1 2 6 10 输出样例1 7 输入样例2 4 6 72 8 4 输出样例2 12 输入样例3 1 7 输出样例3 1