把两头奶牛落到同一厩等价为编号差是 K 的倍数，先记录所有差值，再找最小的不整除任何差值的 K。
OJ: luogu
题目 ID: P1154
难度:普及+/提高
标签:数学枚举思维
日期: 2026-06-20 11:44
题意
给出 n 头奶牛的编号 S_i，需要找一个最小的 K，使得所有奶牛按
S_i mod K
分配厩时，不会有两头奶牛分到同一个厩。
也就是说，所有奶牛对 K 取模后的结果必须两两不同。
思路
先看一个最直接的小数据暴力：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
int n;
int a[MAXN];
// check(k)：判断当前的 k 是否能让所有奶牛落到不同的厩里。
bool check(int k) {
vector<int> used(k, 0);
for (int i = 1; i <= n; i++) {
int r = a[i] % k;
if (used[r]) {
return false;
}
used[r] = 1;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int mn = a[1], mx = a[1];
for (int i = 2; i <= n; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
// brute.cpp：直接从 n 开始枚举 K，并暴力检查余数是否冲突。
// 这个做法最坏是 O((max-min) * n)，只适合小数据和对拍。
for (int k = n; k <= mx - mn + 1; k++) {
if (check(k)) {
cout << k << '\n';
return 0;
}
}
return 0;
}暴力思路很直接：
- 因为要让
n头奶牛落到不同的厩里，所以K至少从n开始枚举 - 对每个
K，直接检查所有S_i mod K是否有重复
这个方法容易想到，但如果一个一个枚举 K，每次又重新算所有余数，效率不够理想。
关键转化：什么时候会冲突？
两头奶牛 i,j 会落到同一个厩，当且仅当：
S_i mod K = S_j mod K
这等价于：
K | (S_i - S_j)
也就是说：
- 如果某个差值
|S_i - S_j|是K的倍数 - 那么这两头奶牛一定会撞到同一个厩里
于是问题就变成了：
找最小的
K >= n，使得它不是任何一对奶牛编号差值的因子。
如何高效判断一个 K 是否可行？
先把所有差值都记录下来。
设：
diff_exist[d] = true
表示存在一对奶牛的编号差恰好是 d。
那么枚举某个 K 时，只要检查：
K, 2K, 3K, ...
这些倍数里，有没有出现在差值表中。
如果有，说明某个差值能被 K 整除，K 不合法。
如果所有倍数都没出现，说明这个 K 可以让所有余数两两不同。
为什么答案一定存在？
设最大编号差为：
max_diff = max(S) - min(S)
当 K > max_diff 时，任意两头奶牛编号之差都小于 K，又不为 0，所以不可能再满足“差值是 K 的倍数”。
于是：
max_diff + 1一定合法
所以答案一定能找到。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
const int MAXS = 1000000;
int n;
int a[MAXN];
bool diff_exist[MAXS + 5]; // diff_exist[d] 表示是否存在一对奶牛编号差值恰好为 d
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
int max_diff = a[n] - a[1];
// 如果两头奶牛在模 K 意义下落到同一个厩，
// 那么它们的编号差一定是 K 的倍数。
// 所以先把所有可能的差值记录下来。
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
diff_exist[a[j] - a[i]] = true;
}
}
// K 至少要有 n 个不同余数位，所以从 n 开始枚举。
for (int k = n; k <= max_diff; k++) {
bool ok = true;
// 只要某个差值是 k 的倍数，就说明有两头奶牛会撞到同一个厩。
for (int d = k; d <= max_diff; d += k) {
if (diff_exist[d]) {
ok = false;
break;
}
}
if (ok) {
cout << k << '\n';
return 0;
}
}
// 当 K > 最大编号差时，任意两头奶牛的差都小于 K，
// 不可能再同余，所以 max_diff + 1 一定可行。
cout << max_diff + 1 << '\n';
return 0;
}复杂度
- 时间复杂度：
，其中 M = max(S) - min(S) - 空间复杂度：
总结
这题最重要的是把“余数冲突”改写成“差值能被 K 整除”。
一旦完成这个转化，题目就从“重复算模”变成了：
- 先统计所有差值
- 再枚举
K检查它的倍数是否出现
本质是一个很典型的等价转化题。