P1154 奶牛分厩 题解

难度：黄。

思路

我们假设 $x \bmod k == y \bmod k$，那么 $x = nk + a$，$y = mk + a$。我们可以计算出： $$
y - x = (mk + a) - (nk + a)\
$$ $$
y - x = mk - nk\
$$ $$
y - x = (m - n)k\
$$ $$
K | y - x

$$ 从而发现这道题其实就是让我们求一个 $K$ 使得任意两个数的差和差的因数和倍数都不等于 $K$。 所以，我们用 一个 vis 数组统计这些差，然后运用 for 循环进行判断就可以了。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; /* */ int n; int a[50005]; int vis[25000001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 1; i <= n; i ++) { for (int j = i + 1; j <= n; j ++) vis[abs(a[i] - a[j])] = 1; } for (int i = 1; i <= 1e6+1; i ++) { bool flag = true; for (int j = 1; j * i <= 1e6 + 1; j ++) { if (vis[i * j]) { flag = false; break; } } if (flag) { cout << i; return 0; } } return 0; } ```