Paste Search Dynamic
ll solve
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pii pair<ll,ll>
  5.  
  6. ll solve(vector<ll>&a,ll n )
  7. {
  8.     ll Prefix[n + 2];
  9.     ll Suffix[n + 2];
  10.  
  11.     Prefix[1] = a[0];
  12.     for (ll i = 2; i <= n; i += 1) {
  13.         Prefix[i] = __gcd(Prefix[i - 1], a[i - 1]);
  14.     }
  15.  
  16.     Suffix[n] = a[n - 1];
  17.  
  18.  
  19.     for (ll i = n - 1; i >= 1; i -= 1) {
  20.         Suffix[i] = __gcd(Suffix[i + 1], a[i - 1]);
  21.     }
  22.  
  23.     ll ans = max(Suffix[2], Prefix[n - 1]);
  24.  
  25.  
  26.     for (ll i = 2; i < n; i += 1) {
  27.         ans = max(ans, __gcd(Prefix[i - 1], Suffix[i + 1]));
  28.     }
  29.  
  30.     return ans;
  31. }
  32.  
  33. int main()
  34. {
  35.     ll t;  cin>>t;
  36.     while(t--)
  37.     {
  38.         ll n;  cin>>n;
  39.         vector<ll>v(n);
  40.         for(auto &it : v)  cin>>it;
  41.         sort(v.begin(),v.end());
  42.  
  43.         ll ans = solve(v,n);
  44.         ll idx =0;
  45.         bool flag = true;
  46.         for(ll i=0;i<n;i++)
  47.         {
  48.             if(v[i]%ans!=0)
  49.             {
  50.                 idx =i;
  51.                 flag= false;
  52.             }
  53.         }
  54.         if(flag) v[n-1]=ans;
  55.         v[idx]=ans;
  56.         ll sum =0;
  57.         for(ll i=0;i<n;i++)
  58.         {
  59.             sum+=v[i]/ans;
  60.         }
  61.         cout<<sum<<endl;
  62.     }
  63.  
  64. }
Parsed in 0.006 seconds