fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.  We implement exactly the plan described above.
  6.  
  7.  For each test case:
  8.    1) Read n, read array a[1..n].
  9.    2) Compute g = gcd(a[1],a[2],...,a[n]).
  10.    3) Count how many a[i] already equal g.  If cnt > 0, answer = n - cnt.
  11.    4) Otherwise, run a small DP to find the minimum subset-size k whose gcd is exactly g.
  12.       Then answer = (k - 1) + (n - 1) = n + k - 2.
  13. */
  14.  
  15. static int gcd_fast(int x, int y) {
  16.     // Use builtin if available; otherwise do slow version:
  17.     return std::__gcd(x, y);
  18. }
  19.  
  20. int main() {
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int T;
  25.     cin >> T;
  26.     while (T--) {
  27.         int n;
  28.         cin >> n;
  29.         vector<int> a(n);
  30.         for (int i = 0; i < n; i++) {
  31.             cin >> a[i];
  32.         }
  33.  
  34.         // 1) Compute overall gcd g:
  35.         int g = a[0];
  36.         for (int i = 1; i < n; i++) {
  37.             g = gcd_fast(g, a[i]);
  38.         }
  39.  
  40.         // 2) Count how many are already == g:
  41.         int cnt_equal_g = 0;
  42.         for (int i = 0; i < n; i++) {
  43.             if (a[i] == g) cnt_equal_g++;
  44.         }
  45.         if (cnt_equal_g > 0) {
  46.             // We already have cnt_equal_g copies of g,
  47.             // so each of the other (n - cnt_equal_g) must be converted with exactly 1 op each.
  48.             cout << (n - cnt_equal_g) << "\n";
  49.             continue;
  50.         }
  51.  
  52.         // 3) Otherwise, we must “build” our first g by combining some subset.
  53.         //    Use DP: dp[d] = minimal subset-size whose gcd = d.
  54.  
  55.         // We'll store dp in an unordered_map<int,int> for all (d -> min size).
  56.         // Start with dp empty.  Process each a[i] in turn.
  57.         unordered_map<int,int> dp, newdp;
  58.         dp.reserve(n * 4);
  59.         newdp.reserve(n * 4);
  60.  
  61.         const int INF = 1e9;
  62.  
  63.         for (int i = 0; i < n; i++) {
  64.             newdp = dp; 
  65.             //  (copy all old pairs (d -> dp[d]) into newdp)
  66.  
  67.             //  3a) The singleton subset { a[i] } has gcd = a[i], size = 1.
  68.             if (!newdp.count(a[i])) {
  69.                 newdp[a[i]] = 1;
  70.             } else {
  71.                 newdp[a[i]] = min(newdp[a[i]], 1);
  72.             }
  73.  
  74.             //  3b) For each existing gcd-value `old_g` in dp,
  75.             //      form d' = gcd(old_g, a[i]) by adding a[i].
  76.             for (auto &kv : dp) {
  77.                 int old_g = kv.first;
  78.                 int old_size = kv.second;
  79.                 int dprime = gcd_fast(old_g, a[i]);
  80.                 int new_size = old_size + 1;
  81.                 if (!newdp.count(dprime) || newdp[dprime] > new_size) {
  82.                     newdp[dprime] = new_size;
  83.                 }
  84.             }
  85.  
  86.             dp.swap(newdp);
  87.         }
  88.  
  89.         // Now dp[g] is the size k of the smallest subset whose gcd = g.
  90.         int k = dp[g];
  91.         // In order to get our first g, we need (k - 1) gcd-operations on that subset.
  92.         // After that, exactly one position = g, and the other (n - 1) are != g,
  93.         // each of which takes 1 more operation to convert ⇒ total = (k-1) + (n-1).
  94.         int answer = (k - 1) + (n - 1);
  95.         cout << answer << "\n";
  96.     }
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
3
3
12 20 30
6
1 9 1 9 8 1
3
6 14 15
stdout 
4
3
3
https://ideone.com/OkTozC
language:
C++ (gcc 8.3)
created:
7 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!