hdu-6025 (前缀 GCD 后缀 GCD)
最编程
2024-10-05 07:03:11
...
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), L(n + 1), R(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
L[1] = a[1];
for (int i = 2; i <= n; i++)
L[i] = __gcd(L[i - 1], a[i]);
R[n] = a[n];
for (int i = n - 1; i >= 1; i--)
R[i] = __gcd(R[i + 1], a[i]);
int ans = max(L[n - 1], R[2]);
for (int i = 2; i <= n - 1; i++)
ans = max(ans, __gcd(L[i - 1], R[i + 1]));
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}