Đề bài
Thuật toán
- (đang cập nhập)
Code
#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; } |
Speak Your Mind