题意：给定一个N个不同的非负整数（每个数不大于10^6），1<=N<=5000，问找到一个最小的m使得N个数去掉最多x(0<=x<k)个数后能够使得N-x个数%m两两不同。
解法：首先可以给定出一个暴力的方法，那就是枚举所有的m，从1开始，然后统计余数相同的数一共多出来多少个，很明显，当多出来的数大于k时则不满足情况，从小到大枚举m遇到第一个满足要求的返回即可。
但是这样很显然会超时，时间复杂度为O(N*10^6)，这里有一个优化如下：
统计出所有的两两组合差值的情况，如有两个数x,y如果x % m = y %m，那么(x - y) % m = 0，统计差值将在后面的计算中发挥作用。当算法枚举到一个m的时候，那么我们就可以在O(10^6/m)的时间内统计出所有差值满足(x-y)%m=0的组数，只要统计差值为1*m, 2*m, ... , p*m <= 10^6的总数sum即可。那么这个组数与拥有相同余数多出来的数有什么关系呢？如果(x - y) % m = 0只能够说明他们对m的余数相等，但是不能保证sum组的余数均相等或者均不相等。
那么如果所有的sum组每组的余数不同：如sum = 5, m = 13. 存在如下五组：(13, 26), (14, 27), (15, 28), (16, 29), (17, 30)。那么重复的数就是5。
如果所有sum组每组的余数都相同：如sum = 6, m = 13. 存在如下五组：(13, 26), (13, 39), (13, 52), (26, 39), (26, 52), (39, 52)。那么重复的数就是3。而可能的取值就是在这两个数之间的，我们取一个下限，即如果下限超过了k则可以判定退出了。k+1个相同余数的数就将不满足题意，他们一共能够生成：C(2, k+1)种组合情况，所以每次验证之前加上这个验证即可。
时间复杂度暂时不知道如何计算。
代码如下：
#include#include #include #include #include using namespace std;int gap[1000005];int N, K;int seq[5005];char lef[1000005];int main() { int MM, cnt, sum; while (scanf("%d %d", &N, &K) != EOF) { MM = -1; memset(gap, 0, sizeof (gap)); for (int i = 0; i < N; ++i) { scanf("%d", &seq[i]); MM = max(MM, seq[i]); } for (int i = 0; i < N; ++i) { for (int j = 0; j < i; ++j) { // 无重复选出两两组合 ++gap[abs(seq[i] - seq[j])]; } } MM = MM + 1; int flag = 0; for (int m = 1; m <= MM && !flag; ++m) { cnt = sum = 0; for (int i = m; i <= MM; i += m) { sum += gap[i]; if (sum > K*(K+1)/2) break; } if (sum > K*(K+1)/2) continue; flag = m; for (int i = 0; i < N; ++i) { int k = seq[i] % m; if (!(lef[k])) lef[k] = 1; else if(++cnt > K) { // cnt用于统计重复度 flag = 0; break; } } for (int i = 0; i < N; ++i) { lef[seq[i] % m] = 0; } } printf("%d\n", flag); } return 0;}