VO17LAN – spoj

Đề bài

• http://vn.spoj.com/problems/VO17LAN/

Thuật toán

• (đang cập nhập)

Code

• xem code trên ideone

#include 
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<