fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod= 998244353;
  5. const ll INF = 100000000;
  6. const int N = 1e6+7;
  7. const int MAXV = 5000;
  8.  
  9.     void solve() {
  10.         int n;
  11.         cin >> n;
  12.         vector<int> a(n);
  13.         for(int i=0;i<n;i++) cin >> a[i];
  14.         int g = a[0];
  15.         for(int i=1;i<n;i++) g=__gcd(a[i],g);
  16.         int cnt = 0;
  17.         for(int i=0;i<n;i++){
  18.             if(a[i]==g) cnt++;
  19.         }
  20.         if(cnt>0){
  21.             cout << n-cnt << '\n';
  22.             return;
  23.         }
  24.        vector<int> dp(MAXV+1, INF), newdp(MAXV+1, INF);        
  25.        for(int i = 0; i < n; i++) {
  26.           for(int d = 1; d <= MAXV; d++) newdp[d] = dp[d]; 
  27.           newdp[a[i]] = min(newdp[a[i]], 1);
  28.         for(int d = 1; d <= MAXV; d++) {
  29.             if (dp[d] == INF) continue;
  30.             int new_g = __gcd(d, a[i]);
  31.             int new_size = dp[d] + 1;
  32.             newdp[new_g]=min(newdp[new_g],new_size);
  33.         }
  34.         dp.swap(newdp);
  35.         }
  36.         int k = dp[g];
  37.         ll ans = (ll)(k - 1) + (ll)(n - 1);
  38.         cout << ans << "\n"; 
  39.     }
  40. int main(){ 
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.  
  44.     int t;
  45.     cin >> t;
  46.     while (t--) solve();
  47.  
  48.     return 0;
  49. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3
3
12 20 30
6
1 9 1 9 8 1
3
6 14 15
stdout
copy 
4
3
3
https://ideone.com/0QxUlK
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!