fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define FORE(i,a,b) for(int i = a; i <= b; ++i)
  4. #define FORD(i,a,b) for(int i = a; i >= b; --i)
  5. #define FOR(i,a,b) for(int i = a; i < b; ++i)
  6. #define pb push_back
  7. #define endl '\n'
  8. #define ll long long
  9. #define X first
  10. #define Y second
  11.  
  12. const int MAXN = 1e5 * 5;
  13. const int base = 1e9 + 7;
  14. const int N = 55000;
  15.  
  16. int t,n;
  17. int ans;
  18. int a[N];
  19.  
  20. int gcd(int a,int b)
  21. {
  22.     if (b == 0) return a;
  23.     else return gcd(b,a%b);
  24. }
  25.  
  26. void upd(int d)
  27. {
  28.     if (d <= ans) return;
  29.     int gcd1 = a[1];
  30.     int gcd2 = 0;
  31.     FORE(i,2,n)
  32.     {
  33.         if (a[i]%d == 0) gcd1 = gcd(gcd1 , a[i]);
  34.         else
  35.         {
  36.             if (gcd2 == 0) gcd2 = a[i];
  37.             else gcd2 = gcd(gcd2 , a[i]);
  38.         }
  39.         if (gcd2 && min(gcd1 , gcd2) <= ans) return;
  40.     }
  41.     if (gcd2 == 0) gcd2 = gcd1;
  42.     ans = max(ans , min(gcd1 , gcd2));
  43. }
  44.  
  45. int main()
  46. {
  47.     ios_base::sync_with_stdio(0); cin.tie(0);
  48.     //freopen("vo17lan.inp" , "r" , stdin);
  49.     //freopen("vo17lan.out" , "w" , stdout);
  50.     cin>>t;
  51.     while(t--)
  52.     {
  53.         cin>>n;
  54.         FORE(i,1,n) cin>>a[i];
  55.         sort(a+1,a+n+1);
  56.         ans = 1;
  57.         int xx = sqrt(a[1]);
  58.         FORD(d,xx,2)
  59.         if (a[1]%d == 0)
  60.         {
  61.             upd(d);
  62.             upd(a[1]/d);
  63.         }
  64.         upd(a[1]);
  65.         cout<<ans<<endl;
  66.     }
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 3680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KSuD4H
language:
C++14 (gcc 8.3)
created:
7 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!