Sol
首先转化一下题意,即要求有超过一半的数在模 \(k\) 意义下相等。
考虑若 \(x=y \pmod k\),则 \((x-y) \bmod k=0\)。
在序列中随机两个数,记这两个数的差值为 \(val\),那么 \(val\) 满足要求的概率即为 \(\frac{1}{4}\),不满足的概率即为 \(\frac{3}{4}\)。
那么随机 \(k\) 次,出错的概率就是 \((\frac{3}{4})^k\),当 \(k\) 足够大时,出错的概率极小。
枚举 \(val\) 的因数判断是否满足要求即可。
再考虑 \(-1\) 的情况。
即原数列中有超过一半的数相同。
Code
//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
#define int long long
using namespace std;
inline char gc()
{
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
int pos=1,num=0;
char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-') pos=-1;
ch=getchar();
}
while (isdigit(ch))
{
num=num*10+(int)(ch-'0');
ch=getchar();
}
return pos*num;
}
void write(int x)
{
if (x<0)
{
putchar('-');
write(-x);
return;
}
if (x>=10) write(x/10);
putchar(x%10+'0');
}
void writesp(int x)
{
write(x);
putchar(' ');
}
void writeln(int x)
{
write(x);
putchar('\n');
}
const int N=1e3+10,X=1e6+10;
int a[N],n;
bool check(int x)
{
map<int,int> Map;
for (int i=1;i<=n;i++)
{
Map[(a[i]+X*x)%x]++;
if (Map[(a[i]+X*x)%x]>=n/2) return 1;
}
return 0;
}
signed main()
{
srand(time(0));
int T=read();
while (T--)
{
n=read();
for (int i=1;i<=n;i++)
a[i]=read();
sort(a+1,a+n+1);
int cnt=1,flag=0;
for (int i=2;i<=n;i++)
if (a[i]==a[i-1])
{
cnt++;
if (cnt>=n/2)
{
flag=1;
break;
}
}
else cnt=1;
if (flag)
{
puts("-1");
continue;
}
int ans=1;
for (int k=1;k<=1000;k++)
{
int x=rand()%n+1,y=rand()%n+1,now=abs(a[x]-a[y]);
for (int i=1;i*i<=now;i++)
if (now%i==0)
{
if (check(i)) ans=max(ans,i);
if (i*i!=now) if (check(now/i)) ans=max(ans,now/i);
}
}
writeln(ans);
}
}