fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using int64 = long long;
  5.  
  6. // ----- sieve up to 1e6 -----
  7. vector<int> small_primes;
  8. void build_sieve() {
  9.     const int LIM = 1000000;
  10.     vector<bool> is(LIM + 1, true);
  11.     is[0] = is[1] = false;
  12.     for (int i = 2; i <= LIM; ++i) if (is[i]) {
  13.         small_primes.push_back(i);
  14.         if (1LL * i * i <= LIM)
  15.             for (long long j = 1LL * i * i; j <= LIM; j += i) is[(int)j] = false;
  16.     }
  17. }
  18.  
  19. vector<pair<long long,int>> factorize(long long n) {
  20.     vector<pair<long long,int>> f;
  21.     long long x = n;
  22.     for (int p : small_primes) {
  23.         if (1LL * p * p > x) break;
  24.         if (x % p == 0) {
  25.             int c = 0;
  26.             while (x % p == 0) { x /= p; ++c; }
  27.             f.push_back({p, c});
  28.         }
  29.     }
  30.     if (x > 1) f.push_back({x, 1});
  31.     return f;
  32. }
  33.  
  34. int main() {
  35.     ios::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.  
  38.     build_sieve();
  39.  
  40.     int T=1;
  41.     while (T--) {
  42.         int N; 
  43.         cin >> N;
  44.         vector<long long> a(N);
  45.         for (int i = 0; i < N; ++i) cin >> a[i];
  46.  
  47.         // factorize all and count composite numbers
  48.         vector<vector<pair<long long,int>>> F(N);
  49.         int composite_cnt = 0;
  50.         for (int i = 0; i < N; ++i) {
  51.             F[i] = factorize(a[i]);
  52.             bool isPrime = (F[i].size() == 1 && F[i][0].second == 1 && F[i][0].first == a[i]);
  53.             if (!isPrime) composite_cnt++;
  54.         }
  55.  
  56.         // collect distinct primes
  57.         unordered_map<long long,int> idx;
  58.         vector<long long> primes;
  59.         primes.reserve(64);
  60.         for (int i = 0; i < N; ++i)
  61.             for (auto &pe : F[i]) if (!idx.count(pe.first)) {
  62.                 idx[pe.first] = (int)primes.size();
  63.                 primes.push_back(pe.first);
  64.             }
  65.         int P = (int)primes.size();
  66.  
  67.         // exponent table exp[p][i]
  68.         vector<vector<int>> expP(P, vector<int>(N, 0));
  69.         for (int i = 0; i < N; ++i)
  70.             for (auto &pe : F[i]) expP[idx[pe.first]][i] = pe.second;
  71.  
  72.         int FULL = 1 << N;
  73.  
  74.         // precompute max exponent per prime for every subset
  75.         vector<vector<int>> maxExp(P, vector<int>(FULL, 0));
  76.         for (int j = 0; j < P; ++j)
  77.             for (int mask = 1; mask < FULL; ++mask) {
  78.                 int lsb = mask & -mask;
  79.                 int i = __builtin_ctz(lsb);
  80.                 maxExp[j][mask] = max(maxExp[j][mask ^ lsb], expP[j][i]);
  81.             }
  82.  
  83.         // cost[mask] = leaves needed if mask is a chain
  84.         vector<int> cost(FULL, 0);
  85.         for (int mask = 1; mask < FULL; ++mask) {
  86.             long long s = 0;
  87.             for (int j = 0; j < P; ++j) s += maxExp[j][mask];
  88.             cost[mask] = (int)s;
  89.         }
  90.  
  91.         // pairwise divisibility
  92.         vector<vector<char>> divs(N, vector<char>(N, 0));
  93.         for (int i = 0; i < N; ++i)
  94.             for (int j = 0; j < N; ++j)
  95.                 if (i != j) divs[i][j] = (a[j] % a[i] == 0);
  96.  
  97.         // mark chains
  98.         vector<char> isChain(FULL, 0);
  99.         isChain[0] = 1;
  100.         for (int mask = 1; mask < FULL; ++mask) {
  101.             bool ok = true;
  102.             for (int i = 0; i < N && ok; ++i) if (mask & (1 << i))
  103.                 for (int j = i + 1; j < N; ++j) if (mask & (1 << j))
  104.                     if (!(divs[i][j] || divs[j][i])) { ok = false; break; }
  105.             isChain[mask] = ok;
  106.         }
  107.  
  108.         // DP: partition into chains minimizing total leaves
  109.         const int INF = 1e9;
  110.         vector<int> dp(FULL, INF);
  111.         dp[0] = 0;
  112.         for (int mask = 1; mask < FULL; ++mask) {
  113.             int sub = mask;
  114.             while (sub) {
  115.                 if (isChain[sub]) dp[mask] = min(dp[mask], dp[mask ^ sub] + cost[sub]);
  116.                 sub = (sub - 1) & mask;
  117.             }
  118.         }
  119.  
  120.         int leaves = dp[FULL - 1];
  121.  
  122.         // extra root node only if the whole set is NOT a chain
  123.         int extra_root = isChain[FULL - 1] ? 0 : 1;
  124.  
  125.         long long ans = leaves + composite_cnt + extra_root;
  126.         cout << ans << '\n';
  127.     }
  128.     return 0;
  129. }
  130.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
21 6 24
stdout
copy 
10
https://ideone.com/zqtKFB
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!