fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int gcd(int a, int b) 
  4. { 
  5.     if (b == 0) 
  6.         return a; 
  7.     return gcd(b, a % b);  
  8.  
  9. } 
  10. int main() {
  11.     int T;
  12.     cin>>T;
  13.     while(T--) {
  14.     	long N;
  15.     	cin>>N;
  16.     	long a[N];
  17.     	for(int i=0;i<N;i++) cin>>a[i];
  18.     	if (N==2) {
  19.     	    cout<<a[0]+a[1]<<endl;
  20.     	    continue;
  21.     	}
  22.     	sort(a, a+N);
  23.     	map<long,long> m;
  24.     	set<long> s;
  25.     	long GCD, ANS, FINAL=a[0];
  26.     	for (int i=1;i<N;i++) {
  27.     	    GCD = gcd(a[0], a[i]);
  28.     	    m[GCD]++;
  29.     	    s.insert(GCD);
  30.     	}
  31.     	vector<long> v(s.begin(), s.end());
  32.     	for(int i=N-1;i>0;i--) {
  33.     	    GCD=gcd(a[0], a[i]);
  34.     	    if (m[GCD]==1 && v[0]==GCD) {
  35.     	        ANS = a[i]+v[1];
  36.     	    } else {
  37.     	        ANS = a[i]+v[0];
  38.     	    }
  39.     	    FINAL = max(FINAL, ANS);
  40.     	}
  41.     	GCD=a[1];
  42.     	for(int i=2;i<N;i++) GCD=gcd(GCD, a[i]);
  43.     	cout<<max(FINAL, GCD+a[0])<<endl;
  44.     }
  45. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
4
4 4 6 7
stdout
copy 
9
https://ideone.com/XvFoDq
language:
C++14 (gcc 8.3)
created:
4 years 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!