VO17LAN – spoj

#include <bits/stdc++.h>
using namespace std;
#define FORE(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define FOR(i,a,b) for(int i = a; i < b; ++i)
#define pb push_back
#define endl '\n'
#define ll long long
#define X first
#define Y second
 
const int MAXN = 1e5 * 5;
const int base = 1e9 + 7;
const int N = 55000;
 
int t,n;
int ans;
int a[N];
 
int gcd(int a,int b)
{
    if (b == 0) return a;
    else return gcd(b,a%b);
}
 
void upd(int d)
{
    if (d <= ans) return;
    int gcd1 = a[1];
    int gcd2 = 0;
    FORE(i,2,n)
    {
        if (a[i]%d == 0) gcd1 = gcd(gcd1 , a[i]);
        else
        {
            if (gcd2 == 0) gcd2 = a[i];
            else gcd2 = gcd(gcd2 , a[i]);
        }
        if (gcd2 && min(gcd1 , gcd2) <= ans) return;
    }
    if (gcd2 == 0) gcd2 = gcd1;
    ans = max(ans , min(gcd1 , gcd2));
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("vo17lan.inp" , "r" , stdin);
    //freopen("vo17lan.out" , "w" , stdout);
    cin>>t;
    while(t--)
    {
        cin>>n;
        FORE(i,1,n) cin>>a[i];
        sort(a+1,a+n+1);
        ans = 1;
        int xx = sqrt(a[1]);
        FORD(d,xx,2)
        if (a[1]%d == 0)
        {
            upd(d);
            upd(a[1]/d);
        }
        upd(a[1]);
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; #define FORE(i,a,b) for(int i = a; i <= b; ++i) #define FORD(i,a,b) for(int i = a; i >= b; --i) #define FOR(i,a,b) for(int i = a; i < b; ++i) #define pb push_back #define endl '\n' #define ll long long #define X first #define Y second const int MAXN = 1e5 * 5; const int base = 1e9 + 7; const int N = 55000; int t,n; int ans; int a[N]; int gcd(int a,int b) { if (b == 0) return a; else return gcd(b,a%b); } void upd(int d) { if (d <= ans) return; int gcd1 = a[1]; int gcd2 = 0; FORE(i,2,n) { if (a[i]%d == 0) gcd1 = gcd(gcd1 , a[i]); else { if (gcd2 == 0) gcd2 = a[i]; else gcd2 = gcd(gcd2 , a[i]); } if (gcd2 && min(gcd1 , gcd2) <= ans) return; } if (gcd2 == 0) gcd2 = gcd1; ans = max(ans , min(gcd1 , gcd2)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("vo17lan.inp" , "r" , stdin); //freopen("vo17lan.out" , "w" , stdout); cin>>t; while(t--) { cin>>n; FORE(i,1,n) cin>>a[i]; sort(a+1,a+n+1); ans = 1; int xx = sqrt(a[1]); FORD(d,xx,2) if (a[1]%d == 0) { upd(d); upd(a[1]/d); } upd(a[1]); cout<<ans<<endl; } return 0; }