CC_JUL_optimal_denomination
12345678910111213141516171819202122232425262728
#include "bits/stdc++.h"
using namespace std;
int getSum(vector<int> v , int g){
int retVal = 0 ;
for(auto &c : v ) retVal += c/g ;
return retVal ;
}
int main() {
int t ; cin >> t ;
while(t--){
int n ; cin >> n ;
vector<int> v(n , 0 ) ;
for(auto &c : v )cin >> c ;
sort(v.begin() , v.end()) ;
int g = v[0] ;
for(int i = 1; i < n ;i++ )g = __gcd(g , v[i]) ;
v[n-1] = g>v[0] ? g : v[0];
int retVal = getSum(v , v[n-1]) ;
cout << retVal <<"\n" ;
}
return 0;
}
Cpp
INFO