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.
Input
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 ≤ 1012).
Output
Print a single integer — the minimum number of vertices in the divisor tree that contains each of the numbers a i.
Examples
input
2
6 10
output
7
input
4
6 72 8 4
output
12
input
1
7
output
1
Note
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.
Solution:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> using namespace std; const int inf = 1234567; int n; long long a[42]; vector <long long> primes; int f[444]; void go(int t, int v, long long num, vector <int> buckets) { if (v == n) { int sz = buckets.size(); int ft = 1; for (int i=0;i<sz;i++) ft += f[buckets[i]]; int other = primes.size(), divs = 0; for (int i=0;i<other;i++) while (num % primes[i] == 0) { num /= primes[i]; divs++; } if ((t & (t - 1)) == 0 && divs == 1) divs = 0; ft += divs; if (ft < f[t]) f[t] = ft; return; } if (t & (1 << v)) { if (num % a[v] == 0) { vector <int> q = buckets; q.push_back(1 << v); go(t, v + 1, num / a[v], q); } vector <int> q = buckets; int sz = q.size(); for (int i=0;i<sz;i++) { q[i] += (1 << v); go(t, v + 1, num, q); q[i] -= (1 << v); } } else go(t, v + 1, num, buckets); } int main() { cin >> n; for (int i=0;i<n;i++) cin >> a[i]; sort(a, a + n); reverse(a, a + n); primes.clear(); for (int i=0;i<n;i++) { long long x = a[i]; for (long long j = 2; j * j <= x; j++) if (x % j == 0) { primes.push_back(j); while (x % j == 0) x /= j; } if (x > 1) primes.push_back(x); } sort(primes.begin(), primes.end()); primes.resize(unique(primes.begin(), primes.end()) - primes.begin()); for (int t=1;t<(1 << n);t++) { int first = 0; for (int i=0;i<n;i++) if (t & (1 << i)) { first = i; break; } f[t] = inf; vector <int> empty; go(t, first + 1, a[first], empty); } int best = f[(1 << n) - 1]; int g[444]; for (int i=0;i<(1 << n);i++) g[i] = inf; g[0] = 0; for (int i=0;i<(1 << n);i++) for (int j=1;j<(1 << n);j++) if ((i & j) == 0) if (g[i] + f[j] < g[i + j]) g[i + j] = g[i] + f[j]; int other = g[(1 << n) - 1] + 1; if (other < best) best = other; printf("%d\n", best); return 0; }