P1154 奶牛分厩

洛谷

题目描述

农夫约翰有$N(1\le N\le 5000)$头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号$s_i$，所有的奶牛都睡在一个有$K$个厩的谷仓中，厩的编号为$0$到$K-1$。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，$S_i\mathrm{mod}K$的值就是第$i$头奶年所睡的厩的编号。

给出一组奶牛的编号，确定最小的Ｋ使得没有二头或二头以上的奶牛睡在同一厩中。

输入格式

第一行一个正整数$N$，第$2$到$N+1$行每行一个整数表示一头奶牛的编号。

输出格式

一个整数，表示要求的最小的$K$，对所有的测试数据这样的$K$是一定存在的。

样例 #1

样例输入 #1

5 
4 
6 
9 
10 
13
1
2
3
4
5
6

样例输出 #1

8
1

提示

$S_i(1\le S_i\le 1000000)$

#include 
#define LL long long 
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;
const int N = 1000000;
int n;
int a[N];
int b[N];
int main(){
    cin >> n;
    for(int i = 1;i <= n;i ++)
        cin >> a[i];
    int res = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = i + 1;j <= n;j ++ ){
            b[abs(a[i] - a[j])] = 1;
        }
    }
    for(int i = 1;i <= N;i ++){
        bool flag = 1;
        for(int j = i;j <= N;j += i){
            if(b[j] == 1){
                flag = 0;
                break;
            }
        }
        if(flag){
            cout << i << endl;
            break;
        }
    }

    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37