P1154 奶牛分厩

题目描述

农夫约翰有Ｎ（1<=Ｎ<=5000）头奶牛，每头奶牛都有一个唯一的不同于其它奶牛的编号Ｓi，所有的奶牛都睡在一个有Ｋ个厩的谷仓中，厩的编号为０到Ｋ－１。每头奶牛都知道自己该睡在哪一个厩中，因为约翰教会了它们做除法，Ｓi MOD Ｋ的值就是第i头奶年所睡的厩的编号。

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

输入输出格式

输入格式：

 

第一行一个正整数Ｎ，第2到Ｎ＋１行每行一个整数表示一头奶牛的编号。

 

输出格式：

 

单独一行一个整数表示要求的最小的Ｋ，对所有的测试数据这样的Ｋ是一定存在的

 

输入输出样例

输入样例#1：

 

5 4 6 9 10 13

输出样例#1：

 

8

说明

Si(1<=Si<=1000000)

 

 

同余定理，我们考虑，a1,a2，若我们需要让他们两个对一个数取膜的余数不同，我们先来考虑当什么时候这两个数取膜后的余数相同呢？我们如果对a2-a1取膜的话，他们的余数最后一定相等等于a1，这里我们假定a2>a1，以此类推，我们就可以求出答案了

#include
     
      #include
      
       #include
       
        #include
        
         #define N 1000010using namespace std;bool check[N];int n,s[N],maxn;int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();    return x*f;}int main(){    n=read();    for(int i=1;i<=n;i++)     s[i]=read(),maxn=max(maxn,s[i]);    for(int i=1;i<=n;i++)     for(int j=i+1;j<=n;j++)      check[abs(s[i]-s[j])]=true;    for(int i=n;i<=maxn;i++)     if(!check[i])      {         printf("%d",i);         return 0;     }}