看到 \(N\) 这么小，容易想到枚举下标 \(i\) ，设 \(C[j]=|A[i]-A[j]|\)，只要 \(M|C[j]\)，那么 \(A[i]=A[j]\mod M\)。
同时因为若 \(p|M\)，那么可以以 \(p\) 为答案。
所以可以对每个 \(C[j]\) 分解质因数，用 \(map\) 记录有多少个 \(C[j]\) 有某个质因子。
时间复杂度 \(O(N^2\sqrt{N}\log N)\) 显然会 T。
于是注意到我们只需要找到一种方案，而且从方案中任意一个数开始都可以求出具体方案，而且方案中元素个数很多（\(\frac{N}{2}\)）那么就采用随机化算法，每次有 \(\frac{1}{2}\) 的概率成功，跑个 5、6 次绰绰有余。
（但说实话，若是 OI 中遇到这种题，没人敢写随机吧。。。
Notice：可以让随机次数随着 \(N\) 动态改变 ，比如设 \(T=\frac{100000}{N}\)，这样充分利用时限
（注意！！！ \(M!=2\)，所以得让 \(4\) 充当质数，细节还是挺多的。。。）
#include<bits/stdc++.h>
using namespace std;
int a[5005],c[5005];
map<int, int> h;
int n;
inline int work(){
for(int i=2;i<=n;++i)c[i]=abs(a[i]-a[1]);
int maxx=0,id=-1;
h.clear();
for(int i=2;i<=n;++i){
int x=c[i];
for(int j=3;j*j<=c[i];++j){
if(x%j==0){
if(j>2){
h[j]++;
if(h[j]>maxx)maxx=h[j],id=j;
}
while(x%j==0)x/=j;
if(x==1)break;
}
}
if(x>2){
if(x%4!=0&&x%2==0)x/=2;
h[x]++;
if(h[x]>maxx)maxx=h[x],id=x;
}
}
if(maxx+1>n-maxx-1)return id;
else return -1;
}
int main(){
srand((unsigned)time(0));
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
int ans=-1;
int T=100000/3/n;
while(T--){
int x=1ll*rand()*rand()%n+1;
swap(a[x],a[1]);
ans=max(ans,work());
if(ans>0)break;
}
cout<<ans<<endl;
return 0;
}
实际上，求质因子（遍历 \(\sqrt N\)) 和求所有约数（也是 \(\sqrt N\) 级别的）时间上差别不是很大，但求约数好写很多，所以若是无法线性筛预处理，直接求约数更方便。
#include<bits/stdc++.h>
using namespace std;
int a[5005],c[5005];
map<int, int> h;
int n;
inline int work(){
for(int i=2;i<=n;++i)c[i]=abs(a[i]-a[1]);
int maxx=0,id=-1;
h.clear();
for(int i=2;i<=n;++i){
int x=c[i];
for(int j=1;j*j<=c[i];++j){
if(x%j==0){
if(j>2){
h[j]++;
if(h[j]>maxx)maxx=h[j],id=j;
}
if(c[i]/j>2&&j*j!=c[i]){
h[c[i]/j]++;
if(h[c[i]/j]>maxx)maxx=h[c[i]/j],id=c[i]/j;
}
}
}
}
if(maxx+1>n-maxx-1)return id;
else return -1;
}
int main(){
srand((unsigned)time(0));
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
int ans=-1;
int T=50000/3/n;
while(T--){
int x=1ll*rand()*rand()%n+1;
swap(a[x],a[1]);
ans=max(ans,work());
if(ans>0)break;
}
cout<<ans<<endl;
return 0;
}