根据抽屉原理显然m>=(n-K)
于是在[n-K,max(a1..an)+1]的范围中枚举m
考虑K=0的做法...
如果a[i]≡a[j](mod m)，则有m|(a[i]-a[j])，只要O（n²）记录下所有a[i]-a[j]，找在max范围内m的倍数是否出现过就行了。根据调和级数复杂度为O（n²+max log max）
如果K>0
我们记录下m的倍数出现过的次数cnt，如果cnt>k*(k+1)/2说明至少有k+1个数模m同余，显然不可行
如果满足cnt<=k*(k+1)/2，我们求出a[i]%m用数组记录，每种只能保留一个，算一下超过的有多少个，若<=k就可行
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=500010,inf=1e9; int n,K,mx; int a[maxn],v[maxn*2],vis[maxn*2]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int main() { read(n);read(K); if(n+1<=K)return puts("1"),0; for(int i=1;i<=n;i++)read(a[i]),mx=max(mx,a[i]); sort(a+1,a+1+n); for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) v[a[j]-a[i]]++; for(int i=n-K;i<=mx+1;i++) { int cnt=0; for(int j=1;i*j<=mx;j++) cnt+=v[i*j]; if(cnt>(K*(K+1)>>1))continue; cnt=0; for(int j=1;j<=n;j++) { int x=a[j]%i; if(vis[x]!=i)vis[x]=i; else cnt++; } if(cnt<=K)return printf("%d",i),0; } return 0; }