https://codeforces.com/contest/1593/problem/D2
分析
枚举选中的\(n/2\)个数中最小的数,然后枚举大于其的数的所有因子,如果拥有某个因子的数的个数大于\(n/2\),则选中,求符合条件的最大的因子即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3fffffff
int t,n,a[45];
unordered_map<int,int> f;
int judge(int index)
{
f.clear();
int cnt=1;
for(int i=index+1;i<n;i++)
{
int k=a[i]-a[index];
if(k==0)cnt++;
for(int j=1;j*j<=k;j++)
{
if(k%j==0)
{
if(f.find(j)!=f.end())f[j]++;
else f[j]=1;
if(k/j!=j)
{
if(f.find(k/j)!=f.end())f[k/j]++;
else f[k/j]=1;
}
}
}
}
if(cnt>=n/2)return INF;
int maxn=-1;
for(auto x:f)
{
if(x.second+cnt>=n/2)
{
maxn=max(maxn,x.first);
}
}
return maxn;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
int ans=-1;
for(int i=0;i<=n/2;i++)//枚举a[i]
{
ans=max(ans,judge(i));
}
if(ans!=INF)printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}