【题目描述】
农夫约翰有
N
(
1
≤
N
≤
5000
)
N(1 \leq N \leq 5000)
N(1≤N≤5000)头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号
s
i
s_i
si ，所有的奶牛都睡在一个有
K
K
K个厩的谷仓中，厩的编号为
0
0
0到
K
−
1
K−1
K−1。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，
S
i
m
o
d
K
S_i \bmod K
SimodK的值就是第
i
i
i头奶牛所睡的厩的编号。
给出一组奶牛的编号，确定最小的
K
K
K使得没有两头或两头以上的奶牛睡在同一厩中。
【输入格式】
第一行一个正整数
N
N
N，第
2
2
2到
N
+
1
N+1
N+1行每行一个整数表示一头奶牛的编号。
【输出格式】
一个整数，表示要求的最小的
K
K
K，对所有的测试数据这样的
K
K
K是一定存在的。
【数据范围】
1
≤
S
i
≤
1000000
1\leq S_i\leq 1000000
1≤Si≤1000000
【输入样例】
5
4
6
9
10
13
【输出样例】
8
【分析】
首先
a
,
b
a,b
a,b在
m
o
d
k
mod\ k
mod k意义下同余，当且仅当
k
∣
(
a
−
b
)
k|(a-b)
k∣(a−b)即
k
k
k是
(
a
−
b
)
(a-b)
(a−b)的一个因子。
这个证明可以考虑
m
o
d
mod
mod运算的意义。也可以
a
%
k
=
b
%
k
a\% k=b\% k
a%k=b%k等价于
a
−
b
=
0
(
m
o
d
k
)
a-b=0(mod\ k)
a−b=0(mod k)。
因为
s
≤
1
0
6
s\leq 10^6
s≤106所以可以预处理出所有差值，并把他们打上标记。
接着从
n
n
n开始从小到大枚举，如果一个数
x
x
x未被标记，那么我们就看他的所有倍数（不超过
K
K
K）是否被标记。如果都没被标记，则说明
x
x
x是合法的，输出
x
x
x即可。
【代码】
#include <iostream>
#include <cmath>
using namespace std;
const int N = 5010, K = 1000010;
int a[N];
bool st[K];//标记a-b
int n;
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
//预处理所有数之间的差值a-b
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
st[abs(a[i] - a[j])] = true;
//从小到大枚举k
for (int i = n; i < K; i++)
if (!st[i])
{
bool flag = true;
for (int j = i + i; j < K; j += i)//判断i是否是a-b的因子
if (st[j])
{
flag = false;
break;
}
if (flag)
{
cout << i << endl;
break;
}
}
return 0;
}