P1154 奶牛分厩

•  
• 173通过
• 481提交
• 题目提供者该用户不存在
• 标签高性能
• 难度普及-
• 时空限制1s / 128MB

 提交  讨论  题解  

最新讨论更多讨论

• 测试点3？？？
• 求助！超时了
• 我抗议！！！

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

5

4

6

9

10

13

输出样例#1：

8

说明

Si(1<=Si<=1000000)

 分析：其实a ≡ b (mod p)就相当于(a - b) % p = 0,一个暴力的想法是枚举k,然后枚举a,b,看有没有b-a = k的倍数,这样的复杂度是O(n^2)的，常数非常大，不能通过，考虑对枚举的优化，哪些才是有用的枚举呢？显然我们可以只看k的倍数有没有在b-a中出现过，我们只需要先枚举一个b-a的vis数组即可.

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n, a[5010],vis[1000010];int main(){    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%d", &a[i]);    sort(a + 1, a + 1 + n);    for (int i = 1; i <= n; i++)        for (int j = i + 1; j <= n; j++)            vis[a[j] - a[i]] = 1;    for (int k = 2; k <= a[n]; k++)    {        bool flag = false;        if (vis[k])            continue;        int t = k * 2;        while (t <= a[n])        {            if (vis[t])            {                flag = true;                break;            }            t += k;        }        if (!flag)        {            printf("%d\n", k);            break;        }    } return 0;}