CF303C Minimum Modular 题解
Super_Cube
2024-11-19 20:26:50
Solution
因为答案最大不超过值域，考虑枚举 m。
时间复杂度好像是 $O(n^2+V\ln V+k^2V)$。
# Code
```cpp
#include<bits/stdc++.h>
int cnt[1000005];
int vis[1000005];
int a[5005];
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
for(int j=i-1;j;--j)
++cnt[std::abs(a[i]-a[j])];
}
for(int i=1,sum;i<=1000000;++i){
sum=0;
for(int j=i;sum<=(m*(m+1)>>1)&&j<=1000000;j+=i)sum+=cnt[j];
if(sum>(m*(m+1)>>1))continue;
sum=0;
for(int j=1;j<=n;++j)
if(vis[a[j]%i]!=i)vis[a[j]%i]=i;
else if(++sum==m+1)break;
if(sum!=m+1)return 0&printf("%d",i);
}
return 0;
}
```