C++ 解法, 执行用时: 824ms, 内存消耗: 82656K, 提交时间: 2021-11-28 21:17:21

#include<iostream>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<map>
#define ll long long 
const int maxn=5e6+7;
using namespace std;
map <ll,ll>	ma,vis;
ll a[maxn],visit[maxn]={0},su[maxn]={0},ans=0,n,num[maxn];
ll read() {	//快读 
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*w;
}
ll fun()
{	long long i,j,k;
	for(i=0;i<=maxn;i++)	visit[i]=0;
	k=0;visit[1]=1;
	for(i=2;i<=maxn;i++)	
	{	if(!visit[i])
		{	su[++k]=i;
			for(j=i*i;j<=n;j+=i)	visit[j]=1;	//筛掉非素数 
		}
	}
	return k;	//返回素数的个数 
}
void getans(ll x)
{	if((double)x*ans*(ans-1)/2>1e13) return;
	if(vis[x]) return;
	vis[x]=1;
	ll i,j,k;
	if(x<=1e6)
	{	for(i=1;i<=n;i++)	num[a[i]%x]++;	
		for(i=1;i<=n;i++) 
		{	if(num[a[i]%x]>ans) ans=num[a[i]%x];
			num[a[i]%x]=0;
		}	
		return;
	}
	for(i=1;i<=n;i++)	ma[a[i]%x]++;
	for(i=1;i<=n;i++)	if(ma[a[i]%x]>ans) ans=ma[a[i]%x];
	ma.clear();
}
int main()
{	ll i,j,k,T=20,x,y,d;
	n=read();
	for(i=1;i<=n;i++)	a[i]=read();
	srand((ll)time(0));
	getans(2);
	k=fun();
	while(T--)
	{	x=rand()%n+1;
		y=rand()%n+1;
		d=abs(a[x]-a[y]);
		for(i=1;i<=k&&su[i]<=d;i++)
		{	if(d%su[i]==0)
			{	getans(su[i]);
				while(d%su[i]==0) d/=su[i];
			}	
		}
		if(d>1)	getans(d);
	}
	cout<<ans<<endl;
	return 0;
}